Changeset 592:e72bacfea6b7 in lemon
 Timestamp:
 02/25/09 12:10:57 (12 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
 1 moved
Legend:
 Unmodified
 Added
 Removed

lemon/Makefile.am
r590 r592 69 69 lemon/full_graph.h \ 70 70 lemon/glpk.h \ 71 lemon/gomory_hu _tree.h \71 lemon/gomory_hu.h \ 72 72 lemon/graph_to_eps.h \ 73 73 lemon/grid_graph.h \ 
lemon/gomory_hu.h
r591 r592 64 64 typename CAP = typename GR::template EdgeMap<int> 65 65 > 66 class GomoryHu Tree{66 class GomoryHu { 67 67 public: 68 68 … … 117 117 /// \param graph The graph the algorithm will run on. 118 118 /// \param capacity The capacity map. 119 GomoryHu Tree(const Graph& graph, const Capacity& capacity)119 GomoryHu(const Graph& graph, const Capacity& capacity) 120 120 : _graph(graph), _capacity(capacity), 121 121 _pred(0), _weight(0), _order(0) … … 128 128 /// 129 129 /// Destructor 130 ~GomoryHu Tree() {130 ~GomoryHu() { 131 131 destroyStructures(); 132 132 } … … 341 341 342 342 /// This iterator class lists the nodes of a minimum cut found by 343 /// GomoryHu Tree. Before using it, you must allocate a GomoryHuTreeclass,344 /// and call its \ref GomoryHu Tree::run() "run()" method.343 /// GomoryHu. Before using it, you must allocate a GomoryHu class, 344 /// and call its \ref GomoryHu::run() "run()" method. 345 345 /// 346 346 /// This example counts the nodes in the minimum cut separating \c s from 347 347 /// \c t. 348 348 /// \code 349 /// GomoruHu Tree<Graph> gom(g, capacities);349 /// GomoruHu<Graph> gom(g, capacities); 350 350 /// gom.run(); 351 351 /// int sum=0; 352 /// for(GomoruHu Tree<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum;352 /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum; 353 353 /// \endcode 354 354 class MinCutNodeIt … … 362 362 /// Constructor 363 363 /// 364 MinCutNodeIt(GomoryHu Treeconst &gomory,365 ///< The GomoryHu Treeclass. You must call its364 MinCutNodeIt(GomoryHu const &gomory, 365 ///< The GomoryHu class. You must call its 366 366 /// run() method 367 367 /// before initializing this iterator … … 438 438 439 439 /// This iterator class lists the edges of a minimum cut found by 440 /// GomoryHu Tree. Before using it, you must allocate a GomoryHuTreeclass,441 /// and call its \ref GomoryHu Tree::run() "run()" method.440 /// GomoryHu. Before using it, you must allocate a GomoryHu class, 441 /// and call its \ref GomoryHu::run() "run()" method. 442 442 /// 443 443 /// This example computes the value of the minimum cut separating \c s from 444 444 /// \c t. 445 445 /// \code 446 /// GomoruHu Tree<Graph> gom(g, capacities);446 /// GomoruHu<Graph> gom(g, capacities); 447 447 /// gom.run(); 448 448 /// int value=0; 449 /// for(GomoruHu Tree<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e)449 /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e) 450 450 /// value+=capacities[e]; 451 451 /// \endcode 452 452 /// the result will be the same as it is returned by 453 /// \ref GomoryHu Tree::minCostValue() "gom.minCostValue(s,t)"453 /// \ref GomoryHu::minCostValue() "gom.minCostValue(s,t)" 454 454 class MinCutEdgeIt 455 455 { … … 471 471 472 472 public: 473 MinCutEdgeIt(GomoryHu Treeconst &gomory,474 ///< The GomoryHu Treeclass. You must call its473 MinCutEdgeIt(GomoryHu const &gomory, 474 ///< The GomoryHu class. You must call its 475 475 /// run() method 476 476 /// before initializing this iterator 
test/gomory_hu_test.cc
r591 r592 4 4 #include <lemon/smart_graph.h> 5 5 #include <lemon/lgf_reader.h> 6 #include <lemon/gomory_hu _tree.h>6 #include <lemon/gomory_hu.h> 7 7 #include <cstdlib> 8 8 … … 61 61 edgeMap("capacity", capacity).run(); 62 62 63 GomoryHu Tree<Graph> ght(graph, capacity);63 GomoryHu<Graph> ght(graph, capacity); 64 64 ght.init(); 65 65 ght.run(); … … 76 76 77 77 int sum=0; 78 for(GomoryHu Tree<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)78 for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) 79 79 sum+=capacity[a]; 80 80 check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); 81 81 82 82 sum=0; 83 for(GomoryHu Tree<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)83 for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n) 84 84 sum++; 85 for(GomoryHu Tree<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)85 for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n) 86 86 sum++; 87 87 check(sum == countNodes(graph), "Problem with MinCutNodeIt");
Note: See TracChangeset
for help on using the changeset viewer.