Thread: Disjoint Sets

  1. #1
    Registered User
    Join Date
    Nov 2002
    Posts
    14

    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.

  2. #2
    Registered User
    Join Date
    Nov 2002
    Posts
    14
    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.

  3. #3
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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
    for adjacent squares.

  4. #4
    Registered User
    Join Date
    Nov 2002
    Posts
    14
    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.

  5. #5
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

  6. #6
    Registered User
    Join Date
    Nov 2002
    Posts
    14
    A[x / d][y / d] what is d here

  7. #7
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    "distance between less than a predefined number."

  8. #8
    Registered User
    Join Date
    Nov 2002
    Posts
    14
    no its suppose to be the distance between point 1 and point 2, that distance has to be less then a predefined number

  9. #9
    Registered User
    Join Date
    Nov 2002
    Posts
    14
    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.

  10. #10
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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. #11
    Registered User
    Join Date
    Nov 2002
    Posts
    14
    Nick i want tosay thank u for helping i will look over what u said and try to understand it

  12. #12
    Registered User
    Join Date
    Nov 2002
    Posts
    14
    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:perator =(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

  13. #13
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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);
    }

  14. #14
    Registered User
    Join Date
    Nov 2002
    Posts
    14
    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);
    }

  15. #15
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

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, 11:05 AM
  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