Implement a Modified Gale Shapley Algorithm.

Given a set of 2n points in a plane, consider a situation where a modified version of the Gale-Shapley algorithm is used to achieve Stable Matching. A point, A, ranks the other 2n1 points in the increasing order of their Euclidean distances from A. Thus, in the preference list of A, the point which is at a minimum distance from A is ranked first. This approach is followed by each of the 2n points in order to rank the other 2n1 points on their preference list. The following pseudo code describes the modified Gale-Shapley algorithm and we also provide a basic description:

During each iteration, a free point, A proposes to another point based on its own ((A's) preference list. However, an engaged point can break up from its current partner if a point ranked higher in its preference list proposes to it.

The total number of points is 2n and is, thus, an even number. Any free point can propose to any of the remaining 2n1 points.

Modified Gale-Shapley algorithm for Stable Matching of points in a plane:

Initially all pP are free While{there is a point that is free and has not proposed to every other point} Choose such a point p Let qP be the highest ranked point in p's preference list to which P has not yet proposed If {q is free} (p,q) become engaged Else q is currently engaged to p If{(Distance of p from q) > (Distance of p from q)} p remains free Else (Distance of p from q) < (Distance of p from q) (p,q) become engaged p becomes free EndIf EndIf EndWhile Return the set S of engaged pairs.

Implement the above algorithm in the function getPointPairs:

This function takes a set of points as input [[x1,y1], [x2, y2] ...[x2n, y2n]]

Return value should be in the form [[[x11, y11], [x12, y12]], [[x21, y21], [x22, y22]] ... [[xn1, yn1], [xn2, yn2]]]

Code the Gale Shapely algorithm for the problem. Implement the function getPointPairs.

Code:

#include #include #include #include #include #include #include #include #include

double pointDistance(double x1, double y1, double x2, double y2)

{ return sqrt( (x2 - x1) * (x2 - x1) + (y2 - y1)* (y2 - y1) ); }

typedef std::pair POINT; typedef std::pair PAIRING;

bool check_stability(std::vector &pairings) { for (int i=0; i< pairings.size(); i++) { for (int j=0; j < pairings.size(); j++) { if (i == j) continue; auto pointpair1 = pairings[i]; auto pointpair2 = pairings[j]; auto pointpair1distance = pointDistance(pointpair1.first.first, pointpair1.first.second,pointpair1.second.first, pointpair1.second.second ); auto pointpair2distance = pointDistance(pointpair2.first.first, pointpair2.first.second,pointpair2.second.first, pointpair2.second.second ); // Any cross distances between the point pairs should be greater than the smaller of the two pointpair?distance auto shorterDistance = pointpair1distance; if (pointpair2distance < shorterDistance ) shorterDistance = pointpair2distance; auto dist = pointDistance(pointpair1.first.first, pointpair1.first.second, pointpair2.second.first, pointpair2.second.second ); if (dist < shorterDistance) return false; dist = pointDistance(pointpair1.first.first, pointpair1.first.first, pointpair2.first.first, pointpair2.first.first ); if (pointDistance(pointpair1.first.first, pointpair1.first.second, pointpair2.first.first, pointpair2.first.second ) < shorterDistance) return false; dist = pointDistance(pointpair1.second.first, pointpair1.second.second, pointpair2.second.first, pointpair2.second.second ); if (pointDistance(pointpair1.second.first, pointpair1.second.second, pointpair2.second.first, pointpair2.second.second ) < shorterDistance) return false; dist = pointDistance(pointpair1.second.first, pointpair1.second.second, pointpair2.first.first, pointpair2.first.second ); if (pointDistance(pointpair1.second.first, pointpair1.second.second, pointpair2.first.first, pointpair2.first.second ) < shorterDistance) return false; } } return true; }

std::vector getPointPairs(std::vector &allPoints) { /* your code here */

// I was thinking of doing something like this std::map > MAP_pt;

// maybe using a map of vectors would be useful, not sure return 0; }

//Additional code that uses my function later on...:

std::vector< POINT > rect = {{0.0,0.0}, {0.0,10.0}, {5.0,0.0}, {5.0,10.0}}; auto pairings = getPointPairs(rect); std::cout << "Stable ? " << (check_stability(pairings));

std::vector trapezoid = {{0.0,0.0}, {10.0, 0.0}, {3.0,5.0}, {7.0,5.0}}; pairings = getPointPairs(trapezoid); std::cout << "Stable ?" << (check_stability(pairings));

bool double_equal(double a, double b) { if ( // Test 1: Very cheap, but can result in false negatives a==b || // Test 2: More expensive, but comprehensive std::abs(a-b)::epsilon()) { return true; } return false; }