# Disjoint Sets

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 11-25-2002
roberto81
Disjoint Sets
I have a question, i have to create a disjointed set from a thousand points (x,y) and the equivalence relation is the distance between two points is less that a predefined number. I am a little lost on the making of the vector in the disjointed set any insight anyone thanks.
• 11-26-2002
roberto81
no i have multiple points (2,30),(4,67),(2,5) .. etc. i have to make a disjoined set and then union two points that have a distance between less than a predefined number. and i have to do it in nlogn not n squared.
• 11-26-2002
Nick
I'm not sure exactly what you want but if you find the maximum
x and maximum y you can then divide the rectangle formed by
the points by drawing dxd lines horizontal and vertical. Then
to tell if any two points are d apart, it's only necessary
to check if they are in the same square or do some checks
• 11-26-2002
roberto81
i dont understand ((x,y) is a point on the euclidean plane)
(2,3) and (2,4) are 1 distance apart from each other by using the distance formula of two points. I dont follow the rectancle thing.
• 11-26-2002
Nick
It's hard to describe without a piece of paper but you can
do something like put (x, y) into A[x / d][y / d] into an 2d array of linked list. Then to union you would put (x2, y2) into the list
A[x2/d][y2 / d] and to do the find operation on (x, y)
it would be the list A[x / d][y / d] and then I think you
would have to check the adjacent lists who's distance
is in the bound.
• 11-26-2002
roberto81
A[x / d][y / d] what is d here
• 11-26-2002
Nick
"distance between less than a predefined number."
• 11-27-2002
roberto81
no its suppose to be the distance between point 1 and point 2, that distance has to be less then a predefined number
• 11-27-2002
roberto81
i know its suppose to be like that but im trying to think of a way to do all possible combinations in less then Order N squared.
• 11-27-2002
Nick
d is the number you are given to find points who's distance
is between. R be the relation (x, y) in R if dist(x, y) <= d.

Draw some points on a piece of paper. Then draw a grid
where each horizontal line and vertical line is d/sqrt(2). (I was
incorrect since you could have points on the corners).
Any points in the same square s are in R but it's also
possible to have points in s and in a adjacent square.
• 11-27-2002
roberto81
Nick i want tosay thank u for helping i will look over what u said and try to understand it
• 11-29-2002
roberto81
Off the top of your head, do you know how to implement a findpathcompression on a object instead of intergers. im have a problem
this is mine;
class Point
{
public:
Point(): x(0),y(0),value(-1),index(0){}
Point(int xCoordinate, // x coordinate in (x,y)
int yCoordinate // y coordinate in (x,y)
): x(xCoordinate), y(yCoordinate),value(-1),index(0) {}
Point(const Point & rhs): x(rhs.x), y(rhs.y), index(rhs.index),
value(rhs.value) {}//Copy Constructor

Point & operator =(const Point & rhs);

int x;
int y;

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

Point& Point::operator =(const Point & rhs)
{
value = rhs.index;
return *this;
}
class DisjSets
{
public:
explicit DisjSets(vector<Point> & a);
Point & findPathcompression( Point & a );//returns the root point and performs
//path compression
void unionSets( Point & a, Point & b );

//private:
vector<Point> s;
};

Point & DisjSets::findPathcompression( Point & a )
{
if( a.value < 0 )
return a;
else
return s[a.index] = findPathcompression(s[a.value]);
}

My findPathcompression doesnt work can you see any problems, thanks alot
• 11-29-2002
Nick
Code:

```Point& Point:perator =(const Point & rhs) { value = rhs.index; return *this; }```
Your copy constructor assigns value to rhs.index.

Code:

```Point & DisjSets::findPathcompression( Point & a ) { if( a.value < 0 ) return a; else return s[a.index] = findPathcompression(s[a.value]); }```
I would make an Point* field parent then all that would
be necessary I think is
Code:

```Point* DisjSets::findPathcompression( Point & a ) {     if( a.parent  == NULL)           return &a;     else           return a.parent = findPathcompression(a.parent); }```
• 11-29-2002
roberto81
CAN YOU EXPLAIN THIS AND EXACTLY WHAT ITS GOING ON IN THE FUNCTION. WHAT IS PARENT AND WHAT TYPE IS IT

i would make an Point* field parent then all that would
be necessary I think is

code:--------------------------------------------------------------------------------
Point* DisjSets::findPathcompression( Point & a )
{
if( a.parent == NULL)
return &a;
else
return a.parent = findPathcompression(a.parent);
}
• 11-29-2002
Nick
This is a tree structure
so that each Point has a pointer to it's parent a Point*.
The parent of the root is null. What the find function
then does is returns the root node and assigns all other
node's parent along the path to the root. So what I did was say
if a's parent is null then were at the root and so we don't need to
adjust anymore nodes. Otherwise we set the parent
node to the result of calling the function on the parent.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last