Topological sort for a grid of arbitrary points?

Question

I have a grid of points x,y where you can move from one point to an immediately visible point as long as the new point has either a greater x, y, or both. How would I sort this topologically?

Answer 1

Because this is a transitive relation (i.e. if you can go from a to b, and b to c, then you must be able to go from a to c) you can simply sort your points to achieve a topological ordering.

For example, this C code would perform a topological sort of an array of points by ordering the points based on the first coordinate, or by the second coordinate if the first coordinate matches.

int C[1000][2];

int compar(const void*a,const void*b)
{
  int *a2=(int*)a;
  int *b2=(int*)b;
  int d=a2[0]-b2[0];
  if (d)
    return d;  // Sort on first coordinate
  return a2[1]-b2[1];  // Sort on second coordinate
}

...
qsort(C,1000,sizeof(int)*2,compar);
...

For your example (0,0) (1,99) (9,16) (16,9) (36,64) (64,36) (100,100), these points are already sorted according to the first coordinate so this would be the output of the call to qsort.

This approach works because if you can go from a to b, then a must either have a smaller x (and so appears earlier in the list), or the same x and a smaller y (and again appears earlier in the sorted list).