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).

Answer 2

There are a huge number of topological orderings of this grid. However, some of them are very easy to compute without any space overhead:

1. Iterate across the rows from bottom-to-top, left to right.
2. Iterate across the columns from left to right, bottom to top.
3. List all points whose sum of x and y is zero, then whose sum of x and y is 1, etc.

Hope this helps!