Changeset - r592:e72bacfea6b7
« 591:ccd2d3
593:d6b40e »
gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Remane GomoryHuTree to GomoryHu (#66)
1 2 1
default
4 files changed with 22 insertions and 22 deletions:
lemon/Makefile.am
1
1
lemon/gomory_hu.h
16
16
test/gomory_hu_test.cc
5
5
↑ Collapse diff ↑
lemon/Makefile.am
Show white space 6 line context
... ... 
@@ -68,7 +68,7 @@
68 68 
	lemon/euler.h \
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 \
74 74 
	lemon/hypercube_graph.h \
lemon/gomory_hu.h
Show white space 6 line context
... ... 
@@ -63,7 +63,7 @@
63 63 
  template <typename GR,
64 64 
	    typename CAP = typename GR::template EdgeMap<int>
65 65 
            >
66 
  class GomoryHuTree {
66 
  class GomoryHu {
67 67 
  public:
68 68 

			




	69
	69
	
		
    /// The graph type


			




	...
	...
	
		
@@ -116,7 +116,7 @@


			




	116
	116
	
		
    /// Constructor


			




	117
	117
	
		
    /// \param graph The graph the algorithm will run on.


			




	118
	118
	
		
    /// \param capacity The capacity map.


			




	119
	
	
		
    GomoryHuTree(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) 


			




	122
	122
	
		
    {


			




	...
	...
	
		
@@ -127,7 +127,7 @@


			




	127
	127
	
		
    /// \brief Destructor


			




	128
	128
	
		
    ///


			




	129
	129
	
		
    /// Destructor


			




	130
	
	
		
    ~GomoryHuTree() {


			




	
	130
	
		
    ~GomoryHu() {


			




	131
	131
	
		
      destroyStructures();


			




	132
	132
	
		
    }


			




	133
	133
	
		

			




	...
	...
	
		
@@ -340,16 +340,16 @@


			




	340
	340
	
		
    /// Iterate on the nodes of a minimum cut


			




	341
	341
	
		
    


			




	342
	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.


			




	
	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
	
	
		
    /// GomoruHuTree<Graph> gom(g, capacities);


			




	
	349
	
		
    /// GomoruHu<Graph> gom(g, capacities);


			




	350
	350
	
		
    /// gom.run();


			




	351
	351
	
		
    /// int sum=0;


			




	352
	
	
		
    /// for(GomoruHuTree<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


			




	355
	355
	
		
    {


			




	...
	...
	
		
@@ -361,8 +361,8 @@


			




	361
	361
	
		

			




	362
	362
	
		
      /// Constructor


			




	363
	363
	
		
      ///


			




	364
	
	
		
      MinCutNodeIt(GomoryHuTree const &gomory,


			




	365
	
	
		
                   ///< The GomoryHuTree class. You must call its


			




	
	364
	
		
      MinCutNodeIt(GomoryHu const &gomory,


			




	
	365
	
		
                   ///< The GomoryHu class. You must call its


			




	366
	366
	
		
                   ///  run() method


			




	367
	367
	
		
                   ///  before initializing this iterator


			




	368
	368
	
		
                   const Node& s, ///< Base node


			




	...
	...
	
		
@@ -437,20 +437,20 @@


			




	437
	437
	
		
    /// Iterate on the edges of a minimum cut


			




	438
	438
	
		
    


			




	439
	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.


			




	
	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
	
	
		
    /// GomoruHuTree<Graph> gom(g, capacities);


			




	
	446
	
		
    /// GomoruHu<Graph> gom(g, capacities);


			




	447
	447
	
		
    /// gom.run();


			




	448
	448
	
		
    /// int value=0;


			




	449
	
	
		
    /// for(GomoruHuTree<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 GomoryHuTree::minCostValue() "gom.minCostValue(s,t)"


			




	
	453
	
		
    /// \ref GomoryHu::minCostValue() "gom.minCostValue(s,t)"


			




	454
	454
	
		
    class MinCutEdgeIt


			




	455
	455
	
		
    {


			




	456
	456
	
		
      bool _side;


			




	...
	...
	
		
@@ -470,8 +470,8 @@


			




	470
	470
	
		
      }


			




	471
	471
	
		
      


			




	472
	472
	
		
    public:


			




	473
	
	
		
      MinCutEdgeIt(GomoryHuTree const &gomory,


			




	474
	
	
		
                   ///< The GomoryHuTree class. You must call its


			




	
	473
	
		
      MinCutEdgeIt(GomoryHu const &gomory,


			




	
	474
	
		
                   ///< The GomoryHu class. You must call its


			




	475
	475
	
		
                   ///  run() method


			




	476
	476
	
		
                   ///  before initializing this iterator


			




	477
	477
	
		
                   const Node& s,  ///< Base node

			




        

    

    

    

        

            

                

                    test/gomory_hu_test.cc
                

                

                  
                  
                  
                  Show white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -3,7 +3,7 @@


			




	3
	3
	
		
#include "test_tools.h"


			




	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
	
		

			




	9
	9
	
		
using namespace std;


			




	...
	...
	
		
@@ -60,7 +60,7 @@


			




	60
	60
	
		
  GraphReader<Graph>(graph, input).


			




	61
	61
	
		
    edgeMap("capacity", capacity).run();


			




	62
	62
	
		

			




	63
	
	
		
  GomoryHuTree<Graph> ght(graph, capacity);


			




	
	63
	
		
  GomoryHu<Graph> ght(graph, capacity);


			




	64
	64
	
		
  ght.init();


			




	65
	65
	
		
  ght.run();


			




	66
	66
	
		

			




	...
	...
	
		
@@ -75,14 +75,14 @@


			




	75
	75
	
		
      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");


			




	76
	76
	
		

			




	77
	77
	
		
      int sum=0;


			




	78
	
	
		
      for(GomoryHuTree<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(GomoryHuTree<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(GomoryHuTree<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");


			




	88
	88
	
		
      


			




        

    






    
    



    


    

     
    
0 comments (0 inline)