Changeset 534:d6b40ebb2617 in lemon-1.1
- Timestamp:
- 03/04/09 14:56:09 (16 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/gomory_hu.h
r533 r534 37 37 /// \brief Gomory-Hu cut tree algorithm 38 38 /// 39 /// The Gomory-Hu tree is a tree on the node set of thegraph, but it40 /// may contain edges which are not in the original digraph. It has the39 /// The Gomory-Hu tree is a tree on the node set of a given graph, but it 40 /// may contain edges which are not in the original graph. It has the 41 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 digraph42 /// in this tree has the same weight as the minimum cut in the graph 43 43 /// between these nodes. Moreover the components obtained by removing 44 44 /// this edge from the tree determine the corresponding minimum cut. … … 54 54 /// 55 55 /// The members \c minCutMap() and \c minCutValue() calculate 56 /// the minimum cut and the minimum cut value between any two node 57 /// in the digraph. You can also list (iterate on) the nodes and the58 /// edges of the cuts using MinCutNodeIt andMinCutEdgeIt.56 /// the minimum cut and the minimum cut value between any two nodes 57 /// in the graph. You can also list (iterate on) the nodes and the 58 /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt. 59 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. 60 /// \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. 63 #ifdef DOXYGEN 63 64 template <typename GR, 64 typename CAP = typename GR::template EdgeMap<int> 65 > 65 typename CAP> 66 #else 67 template <typename GR, 68 typename CAP = typename GR::template EdgeMap<int> > 69 #endif 66 70 class GomoryHu { 67 71 public: … … 69 73 /// The graph type 70 74 typedef GR Graph; 71 /// The type if the edge capacity map75 /// The type of the edge capacity map 72 76 typedef CAP Capacity; 73 77 /// The value type of capacities … … 115 119 /// 116 120 /// Constructor 117 /// \param graph The graph the algorithm will runon.118 /// \param capacity The capacity map.121 /// \param graph The undirected graph the algorithm runs on. 122 /// \param capacity The edge capacity map. 119 123 GomoryHu(const Graph& graph, const Capacity& capacity) 120 124 : _graph(graph), _capacity(capacity), … … 132 136 } 133 137 134 // \brief Initialize the internal data structures. 135 // 136 // This function initializes the internal data structures. 137 // 138 private: 139 140 // Initialize the internal data structures 138 141 void init() { 139 142 createStructures(); … … 149 152 150 153 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 // 154 // Start the algorithm 157 155 void start() { 158 156 Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID); … … 199 197 } 200 198 199 public: 200 201 201 ///\name Execution Control 202 202 … … 216 216 ///The results of the algorithm can be obtained using these 217 217 ///functions.\n 218 /// The\ref run() "run()" should be called before using them.\n219 ///See also MinCutNodeIt and MinCutEdgeIt218 ///\ref run() "run()" should be called before using them.\n 219 ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt. 220 220 221 221 ///@{ … … 251 251 /// This function returns the minimum cut value between two nodes. The 252 252 /// algorithm finds the nearest common ancestor in the Gomory-Hu 253 /// tree and calculates the minimum weight arcon the paths to253 /// tree and calculates the minimum weight edge on the paths to 254 254 /// the ancestor. 255 255 Value minCutValue(const Node& s, const Node& t) const { … … 272 272 /// 273 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 278 /// "ReadWriteMap". 279 /// 280 /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt 274 /// in the \c cutMap parameter by setting the nodes in the component of 275 /// \c s to \c true and the other nodes to \c false. 276 /// 277 /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt. 281 278 template <typename CutMap> 282 Value minCutMap(const Node& s, ///< Base node279 Value minCutMap(const Node& s, ///< The base node. 283 280 const Node& t, 284 ///< The node you want to separate from Nodes.281 ///< The node you want to separate from node \c s. 285 282 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. 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. 289 287 ) const { 290 288 Node sn = s, tn = t; … … 349 347 /// GomoruHu<Graph> gom(g, capacities); 350 348 /// gom.run(); 351 /// int sum=0;352 /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID;++n) ++sum;349 /// int cnt=0; 350 /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; 353 351 /// \endcode 354 352 class MinCutNodeIt … … 360 358 /// Constructor 361 359 362 /// Constructor 360 /// Constructor. 363 361 /// 364 362 MinCutNodeIt(GomoryHu const &gomory, 365 363 ///< The GomoryHu class. You must call its 366 364 /// run() method 367 /// before initializing this iterator 368 const Node& s, ///< Base node365 /// before initializing this iterator. 366 const Node& s, ///< The base node. 369 367 const Node& t, 370 ///< The node you want to separate from Nodes.368 ///< The node you want to separate from node \c s. 371 369 bool side=true 372 370 ///< If it is \c true (default) then the iterator lists … … 399 397 ++_node_it) {} 400 398 } 401 /// Conversion to Node402 403 /// Conversion to Node399 /// Conversion to \c Node 400 401 /// Conversion to \c Node. 404 402 /// 405 403 operator typename Graph::Node() const … … 411 409 /// Next node 412 410 413 /// Next node 411 /// Next node. 414 412 /// 415 413 MinCutNodeIt &operator++() … … 420 418 /// Postfix incrementation 421 419 422 /// Postfix incrementation 420 /// Postfix incrementation. 423 421 /// 424 422 /// \warning This incrementation 425 /// returns a \c Node, not a \ refMinCutNodeIt, as one may423 /// returns a \c Node, not a \c MinCutNodeIt, as one may 426 424 /// expect. 427 425 typename Graph::Node operator++(int) … … 447 445 /// gom.run(); 448 446 /// int value=0; 449 /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID;++e)447 /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) 450 448 /// value+=capacities[e]; 451 449 /// \endcode 452 450 /// the result will be the same as it is returned by 453 /// \ref GomoryHu::minC ostValue() "gom.minCostValue(s,t)"451 /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)" 454 452 class MinCutEdgeIt 455 453 { … … 474 472 ///< The GomoryHu class. You must call its 475 473 /// run() method 476 /// before initializing this iterator 477 const Node& s, ///< Base node474 /// before initializing this iterator. 475 const Node& s, ///< The base node. 478 476 const Node& t, 479 ///< The node you want to separate from Nodes.477 ///< The node you want to separate from node \c s. 480 478 bool side=true 481 479 ///< If it is \c true (default) then the listed arcs … … 505 503 while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step(); 506 504 } 507 /// Conversion to Arc508 509 /// Conversion to Arc505 /// Conversion to \c Arc 506 507 /// Conversion to \c Arc. 510 508 /// 511 509 operator typename Graph::Arc() const … … 513 511 return _arc_it; 514 512 } 515 /// Conversion to Edge516 517 /// Conversion to Edge513 /// Conversion to \c Edge 514 515 /// Conversion to \c Edge. 518 516 /// 519 517 operator typename Graph::Edge() const … … 525 523 /// Next edge 526 524 527 /// Next edge 525 /// Next edge. 528 526 /// 529 527 MinCutEdgeIt &operator++() … … 535 533 /// Postfix incrementation 536 534 537 /// Postfix incrementation 535 /// Postfix incrementation. 538 536 /// 539 537 /// \warning This incrementation 540 /// returns a \c Arc, not a \ref MinCutEdgeIt, as one may 541 /// expect. 538 /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect. 542 539 typename Graph::Arc operator++(int) 543 540 { -
test/gomory_hu_test.cc
r533 r534 62 62 63 63 GomoryHu<Graph> ght(graph, capacity); 64 ght.init();65 64 ght.run(); 66 65
Note: See TracChangeset
for help on using the changeset viewer.