Disjoint Sets

This is a discussion on Disjoint Sets within the C++ Programming forums, part of the General Programming Boards category; HOW WOULD I IMPLEMENT IT HERE class Point { public: Point(): x(0),y(0),value(-1),index(0) PARENT(NULL){} Point(int xCoordinate, // x coordinate in (x,y) ...

  1. #16
    Registered User
    Join Date
    Nov 2002
    Posts
    14
    HOW WOULD I IMPLEMENT IT HERE

    class Point
    {
    public:
    Point(): x(0),y(0),value(-1),index(0) PARENT(NULL){}
    Point(int xCoordinate, // x coordinate in (x,y)
    int yCoordinate // y coordinate in (x,y)
    ): x(xCoordinate), y(yCoordinate),value(-1),index(0),PARENT(NULL) {}
    Point(const Point & rhs): x(rhs.x), y(rhs.y), index(rhs.index),
    value(rhs.value) PARENT->RHS->PARENT{}//Copy Constructor

    Point & operator =(const Point & rhs);

    POINT * PARENT;
    int x;
    int y;

    int index; //place label
    int value; //value inside place label
    };

    iS THIS THE RIGHT WAY

  2. #17
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    I would go with

    Code:
    class Point {
    public:
           int x;
           int y;
           Point* parent;
    
           Point(int newX, int newY) : x(newX), y(newY) {
                  parent = NULL;
           }
    private:
           // define private since we shouldn't have to call them
           Point& operator=(Point& left, Point& right);
           Point(const Point&);
    };

  3. #18
    Registered User
    Join Date
    Nov 2002
    Posts
    14
    thanks i will check that out and talk to you tommorrow thanks

  4. #19
    Registered User
    Join Date
    Nov 2002
    Posts
    14
    How would i do union by size with parent

    i would have to do parent->point.value = negative what ever right

  5. #20
    Registered User
    Join Date
    Nov 2002
    Posts
    14
    nick when i create does functions there is conflict because we are use a pointer with a reference

    Code:
    Point* DisjSets::findPathcompression( Point & a )
    {
         if( a.parent  == NULL)
              return &a;
         else
              return a.parent = findPathcompression(a.parent);
    }
    i still can get it to work correctly my union sets is wrong

    my union set by size is
    Code:
    		void DisjSets::unionSets( Point & a, Point & b )
            {
                int indexA = findPathcompression(a);
    			int indexB = findPathcompression(b);
    
    			if(s[indexA].value < s[indexB].value ||
    				s[indexA].value == s[indexB].value)
    			{
    				s[indexA].value += s[indexB].value;
    				s[b.index].value = s[indexA].index;
    			}
    			else
    			{
    				s[indexB].value += s[indexA].value;
    					s[a.index].value = s[indexB].index;
    			}
    
    }
    i made the path compression send an int out

    Code:
    		int DisjSets::findPathcompression( Point & a )
            {
                if( a.value < 0 )
                    return a.index;
                else
                    return s[a.index].value = findPathcompression(s[a.value]);
            }
    my = operator is correct
    Code:
    Point& Point::operator =(const Point & rhs)
    {
    	
    	rhs.value = index;
    	return *this;
    }

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem aligning floating point numbers
    By esbo in forum C Programming
    Replies: 4
    Last Post: 01-05-2009, 08:09 PM
  2. Major Problems with GetSaveFileName() and GetOpenFileName()
    By CodeHacker in forum Windows Programming
    Replies: 8
    Last Post: 07-12-2004, 12:05 PM
  3. disjoint sets conceptual question
    By axon in forum C++ Programming
    Replies: 1
    Last Post: 03-01-2004, 10:49 PM
  4. creating new sets
    By axon in forum C++ Programming
    Replies: 7
    Last Post: 12-03-2003, 06:37 PM
  5. Disjoint Sets
    By roberto81 in forum C++ Programming
    Replies: 0
    Last Post: 11-23-2002, 11:57 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21