Changeset 591:ccd2d3a3001e in lemon for lemon/gomory_hu_tree.h
 Timestamp:
 02/25/09 12:10:52 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/gomory_hu_tree.h
r590 r591 22 22 #include <limits> 23 23 24 #include <lemon/core.h> 24 25 #include <lemon/preflow.h> 25 26 #include <lemon/concept_check.h> … … 36 37 /// \brief GomoryHu cut tree algorithm 37 38 /// 38 /// The GomoryHu tree is a tree on the nodeset of the digraph, but it 39 /// may contain arcs which are not in the original digraph. It helps 40 /// to calculate the minimum cut between all pairs of nodes, because 41 /// the minimum capacity arc on the tree path between two nodes has 42 /// the same weight as the minimum cut in the digraph between these 43 /// nodes. Moreover this arc separates the nodes to two parts which 44 /// determine this minimum cut. 39 /// The GomoryHu tree is a tree on the node set of the graph, but it 40 /// may contain edges which are not in the original digraph. It has the 41 /// property that the minimum capacity edge of the path between two nodes 42 /// in this tree has the same weight as the minimum cut in the digraph 43 /// between these nodes. Moreover the components obtained by removing 44 /// this edge from the tree determine the corresponding minimum cut. 45 /// 46 /// Therefore once this tree is computed, the minimum cut between any pair 47 /// of nodes can easily be obtained. 45 48 /// 46 /// The algorithm calculates \e n1 distin ict minimum cutswith47 /// preflow algorithm, therefore the algorithm has49 /// The algorithm calculates \e n1 distinct minimum cuts (currently with 50 /// the \ref Preflow algorithm), therefore the algorithm has 48 51 /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a 49 /// rooted GomoryHu tree, the structure of the tree and the weights 50 /// can be obtained with \c predNode() and \c predValue() 51 /// functions. The \c minCutValue() and \c minCutMap() calculates 52 /// rooted GomoryHu 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 52 56 /// the minimum cut and the minimum cut value between any two node 53 /// in the digraph. 54 template <typename _Graph, 55 typename _Capacity = typename _Graph::template EdgeMap<int> > 57 /// in the digraph. You can also list (iterate on) the nodes and the 58 /// edges of the cuts using MinCutNodeIt and MinCutEdgeIt. 59 /// 60 /// \tparam GR The undirected graph data structure the algorithm will run on 61 /// \tparam CAP type of the EdgeMap describing the Edge capacities. 62 /// it is typename GR::template EdgeMap<int> by default. 63 template <typename GR, 64 typename CAP = typename GR::template EdgeMap<int> 65 > 56 66 class GomoryHuTree { 57 67 public: 58 68 59 69 /// The graph type 60 typedef _GraphGraph;61 /// The capacity on edges62 typedef _CapacityCapacity;70 typedef GR Graph; 71 /// The type if the edge capacity map 72 typedef CAP Capacity; 63 73 /// The value type of capacities 64 74 typedef typename Capacity::Value Value; … … 105 115 /// 106 116 /// Constructor 107 /// \param graph The graph t ype.117 /// \param graph The graph the algorithm will run on. 108 118 /// \param capacity The capacity map. 109 119 GomoryHuTree(const Graph& graph, const Capacity& capacity) … … 122 132 } 123 133 124 // / \brief Initializesthe internal data structures.125 // /126 // / Initializes the internal data structures.127 // /134 // \brief Initialize the internal data structures. 135 // 136 // This function initializes the internal data structures. 137 // 128 138 void init() { 129 139 createStructures(); … … 139 149 140 150 141 /// \brief Starts the algorithm 142 /// 143 /// Starts the algorithm. 151 // \brief Start the algorithm 152 // 153 // This function starts the algorithm. 154 // 155 // \pre \ref init() must be called before using this function. 156 // 144 157 void start() { 145 158 Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID); … … 186 199 } 187 200 188 /// \brief Runs the GomoryHu algorithm. 189 /// 190 /// Runs the GomoryHu algorithm. 191 /// \note gh.run() is just a shortcut of the following code. 192 /// \code 193 /// ght.init(); 194 /// ght.start(); 195 /// \endcode 201 ///\name Execution Control 202 203 ///@{ 204 205 /// \brief Run the GomoryHu algorithm. 206 /// 207 /// This function runs the GomoryHu algorithm. 196 208 void run() { 197 209 init(); 198 210 start(); 199 211 } 200 201 /// \brief Returns the predecessor node in the GomoryHu tree. 202 /// 203 /// Returns the predecessor node in the GomoryHu tree. If the node is 212 213 /// @} 214 215 ///\name Query Functions 216 ///The results of the algorithm can be obtained using these 217 ///functions.\n 218 ///The \ref run() "run()" should be called before using them.\n 219 ///See also MinCutNodeIt and MinCutEdgeIt 220 221 ///@{ 222 223 /// \brief Return the predecessor node in the GomoryHu tree. 224 /// 225 /// This function returns the predecessor node in the GomoryHu tree. 226 /// If the node is 204 227 /// the root of the GomoryHu tree, then it returns \c INVALID. 205 228 Node predNode(const Node& node) { … … 207 230 } 208 231 209 /// \brief Returns the weight of the predecessor arc in the 232 /// \brief Return the distance from the root node in the GomoryHu tree. 233 /// 234 /// This function returns the distance of \c node from the root node 235 /// in the GomoryHu tree. 236 int rootDist(const Node& node) { 237 return (*_order)[node]; 238 } 239 240 /// \brief Return the weight of the predecessor edge in the 210 241 /// GomoryHu tree. 211 242 /// 212 /// Returns the weight of the predecessor arc in the GomoryHu 213 /// tree. If the node is the root of the GomoryHu tree, the 214 /// result is undefined. 243 /// This function returns the weight of the predecessor edge in the 244 /// GomoryHu tree. If the node is the root, the result is undefined. 215 245 Value predValue(const Node& node) { 216 246 return (*_weight)[node]; 217 247 } 218 248 219 /// \brief Return sthe minimum cut value between two nodes220 /// 221 /// Returns the minimum cut value between two nodes. The249 /// \brief Return the minimum cut value between two nodes 250 /// 251 /// This function returns the minimum cut value between two nodes. The 222 252 /// algorithm finds the nearest common ancestor in the GomoryHu 223 253 /// tree and calculates the minimum weight arc on the paths to … … 229 259 while (sn != tn) { 230 260 if ((*_order)[sn] < (*_order)[tn]) { 231 if ((*_weight)[tn] < value) value = (*_weight)[tn];261 if ((*_weight)[tn] <= value) value = (*_weight)[tn]; 232 262 tn = (*_pred)[tn]; 233 263 } else { 234 if ((*_weight)[sn] < value) value = (*_weight)[sn];264 if ((*_weight)[sn] <= value) value = (*_weight)[sn]; 235 265 sn = (*_pred)[sn]; 236 266 } … … 239 269 } 240 270 241 /// \brief Return sthe minimum cut between two nodes242 /// 243 /// Returns the minimum cut value between two nodes. The244 /// algorithm finds the nearest common ancestor in the GomoryHu245 /// tree and calculates the minimum weight arc on the paths to246 /// the ancestor. Then it sets all nodes to the cut determined by247 /// this arc.The \c cutMap should be \ref concepts::ReadWriteMap271 /// \brief Return the minimum cut between two nodes 272 /// 273 /// This function returns the minimum cut between the nodes \c s and \c t 274 /// the \r cutMap parameter by setting the nodes in the component of 275 /// \c \s to true and the other nodes to false. 276 /// 277 /// The \c cutMap should be \ref concepts::ReadWriteMap 248 278 /// "ReadWriteMap". 279 /// 280 /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt 249 281 template <typename CutMap> 250 Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const { 282 Value minCutMap(const Node& s, ///< Base node 283 const Node& t, 284 ///< The node you want to separate from Node s. 285 CutMap& cutMap 286 ///< The cut will be return in this map. 287 /// It must be a \c bool \ref concepts::ReadWriteMap 288 /// "ReadWriteMap" on the graph nodes. 289 ) const { 251 290 Node sn = s, tn = t; 252 291 bool s_root=false; 253 292 Node rn = INVALID; 254 293 Value value = std::numeric_limits<Value>::max(); … … 256 295 while (sn != tn) { 257 296 if ((*_order)[sn] < (*_order)[tn]) { 258 if ((*_weight)[tn] < value) {297 if ((*_weight)[tn] <= value) { 259 298 rn = tn; 299 s_root = false; 260 300 value = (*_weight)[tn]; 261 301 } 262 302 tn = (*_pred)[tn]; 263 303 } else { 264 if ((*_weight)[sn] < value) {304 if ((*_weight)[sn] <= value) { 265 305 rn = sn; 306 s_root = true; 266 307 value = (*_weight)[sn]; 267 308 } … … 272 313 typename Graph::template NodeMap<bool> reached(_graph, false); 273 314 reached.set(_root, true); 274 cutMap.set(_root, false);315 cutMap.set(_root, !s_root); 275 316 reached.set(rn, true); 276 cutMap.set(rn, true); 277 317 cutMap.set(rn, s_root); 318 319 std::vector<Node> st; 278 320 for (NodeIt n(_graph); n != INVALID; ++n) { 279 st d::vector<Node> st;280 321 st.clear(); 322 Node nn = n; 281 323 while (!reached[nn]) { 282 324 st.push_back(nn); … … 292 334 } 293 335 336 ///@} 337 338 friend class MinCutNodeIt; 339 340 /// Iterate on the nodes of a minimum cut 341 342 /// This iterator class lists the nodes of a minimum cut found by 343 /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class, 344 /// and call its \ref GomoryHuTree::run() "run()" method. 345 /// 346 /// This example counts the nodes in the minimum cut separating \c s from 347 /// \c t. 348 /// \code 349 /// GomoruHuTree<Graph> gom(g, capacities); 350 /// gom.run(); 351 /// int sum=0; 352 /// for(GomoruHuTree<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum; 353 /// \endcode 354 class MinCutNodeIt 355 { 356 bool _side; 357 typename Graph::NodeIt _node_it; 358 typename Graph::template NodeMap<bool> _cut; 359 public: 360 /// Constructor 361 362 /// Constructor 363 /// 364 MinCutNodeIt(GomoryHuTree const &gomory, 365 ///< The GomoryHuTree class. You must call its 366 /// run() method 367 /// before initializing this iterator 368 const Node& s, ///< Base node 369 const Node& t, 370 ///< The node you want to separate from Node s. 371 bool side=true 372 ///< If it is \c true (default) then the iterator lists 373 /// the nodes of the component containing \c s, 374 /// otherwise it lists the other component. 375 /// \note As the minimum cut is not always unique, 376 /// \code 377 /// MinCutNodeIt(gomory, s, t, true); 378 /// \endcode 379 /// and 380 /// \code 381 /// MinCutNodeIt(gomory, t, s, false); 382 /// \endcode 383 /// does not necessarily give the same set of nodes. 384 /// However it is ensured that 385 /// \code 386 /// MinCutNodeIt(gomory, s, t, true); 387 /// \endcode 388 /// and 389 /// \code 390 /// MinCutNodeIt(gomory, s, t, false); 391 /// \endcode 392 /// together list each node exactly once. 393 ) 394 : _side(side), _cut(gomory._graph) 395 { 396 gomory.minCutMap(s,t,_cut); 397 for(_node_it=typename Graph::NodeIt(gomory._graph); 398 _node_it!=INVALID && _cut[_node_it]!=_side; 399 ++_node_it) {} 400 } 401 /// Conversion to Node 402 403 /// Conversion to Node 404 /// 405 operator typename Graph::Node() const 406 { 407 return _node_it; 408 } 409 bool operator==(Invalid) { return _node_it==INVALID; } 410 bool operator!=(Invalid) { return _node_it!=INVALID; } 411 /// Next node 412 413 /// Next node 414 /// 415 MinCutNodeIt &operator++() 416 { 417 for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {} 418 return *this; 419 } 420 /// Postfix incrementation 421 422 /// Postfix incrementation 423 /// 424 /// \warning This incrementation 425 /// returns a \c Node, not a \ref MinCutNodeIt, as one may 426 /// expect. 427 typename Graph::Node operator++(int) 428 { 429 typename Graph::Node n=*this; 430 ++(*this); 431 return n; 432 } 433 }; 434 435 friend class MinCutEdgeIt; 436 437 /// Iterate on the edges of a minimum cut 438 439 /// This iterator class lists the edges of a minimum cut found by 440 /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class, 441 /// and call its \ref GomoryHuTree::run() "run()" method. 442 /// 443 /// This example computes the value of the minimum cut separating \c s from 444 /// \c t. 445 /// \code 446 /// GomoruHuTree<Graph> gom(g, capacities); 447 /// gom.run(); 448 /// int value=0; 449 /// for(GomoruHuTree<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e) 450 /// value+=capacities[e]; 451 /// \endcode 452 /// the result will be the same as it is returned by 453 /// \ref GomoryHuTree::minCostValue() "gom.minCostValue(s,t)" 454 class MinCutEdgeIt 455 { 456 bool _side; 457 const Graph &_graph; 458 typename Graph::NodeIt _node_it; 459 typename Graph::OutArcIt _arc_it; 460 typename Graph::template NodeMap<bool> _cut; 461 void step() 462 { 463 ++_arc_it; 464 while(_node_it!=INVALID && _arc_it==INVALID) 465 { 466 for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {} 467 if(_node_it!=INVALID) 468 _arc_it=typename Graph::OutArcIt(_graph,_node_it); 469 } 470 } 471 472 public: 473 MinCutEdgeIt(GomoryHuTree const &gomory, 474 ///< The GomoryHuTree class. You must call its 475 /// run() method 476 /// before initializing this iterator 477 const Node& s, ///< Base node 478 const Node& t, 479 ///< The node you want to separate from Node s. 480 bool side=true 481 ///< If it is \c true (default) then the listed arcs 482 /// will be oriented from the 483 /// the nodes of the component containing \c s, 484 /// otherwise they will be oriented in the opposite 485 /// direction. 486 ) 487 : _graph(gomory._graph), _cut(_graph) 488 { 489 gomory.minCutMap(s,t,_cut); 490 if(!side) 491 for(typename Graph::NodeIt n(_graph);n!=INVALID;++n) 492 _cut[n]=!_cut[n]; 493 494 for(_node_it=typename Graph::NodeIt(_graph); 495 _node_it!=INVALID && !_cut[_node_it]; 496 ++_node_it) {} 497 _arc_it = _node_it!=INVALID ? 498 typename Graph::OutArcIt(_graph,_node_it) : INVALID; 499 while(_node_it!=INVALID && _arc_it == INVALID) 500 { 501 for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {} 502 if(_node_it!=INVALID) 503 _arc_it= typename Graph::OutArcIt(_graph,_node_it); 504 } 505 while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step(); 506 } 507 /// Conversion to Arc 508 509 /// Conversion to Arc 510 /// 511 operator typename Graph::Arc() const 512 { 513 return _arc_it; 514 } 515 /// Conversion to Edge 516 517 /// Conversion to Edge 518 /// 519 operator typename Graph::Edge() const 520 { 521 return _arc_it; 522 } 523 bool operator==(Invalid) { return _node_it==INVALID; } 524 bool operator!=(Invalid) { return _node_it!=INVALID; } 525 /// Next edge 526 527 /// Next edge 528 /// 529 MinCutEdgeIt &operator++() 530 { 531 step(); 532 while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step(); 533 return *this; 534 } 535 /// Postfix incrementation 536 537 /// Postfix incrementation 538 /// 539 /// \warning This incrementation 540 /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may 541 /// expect. 542 typename Graph::Arc operator++(int) 543 { 544 typename Graph::Arc e=*this; 545 ++(*this); 546 return e; 547 } 548 }; 549 294 550 }; 295 551
Note: See TracChangeset
for help on using the changeset viewer.