Implementing Kruskal's Algorithm in Python on images

Question

A grid defines an image using edges stored in two arrays:

• h[x][y] gives the edge weight from x,y to x+1,y
• v[x][y] gives the edge weight from x,y to x,y+1

I'm trying to implement Kruskal's algorithm. This is fairly straightforward- I can find implementations online and copy them. The issue is dealing with edges. Specifically; sorting them is confusing.

Is there a better way to store the edges for this take specifically? I want them to be from every pixel to the adjacent pixels. I have the image stored as i[x][y], and the edge weight is just the difference between the image values.

Answer 1

What you need to do is create a list of all the edges and then sort them. To do this, you will need to define a class Edge:

class Edge:
    def x
    def y
    def direction
    def weight

Then, parse the h and v matrices and build up the edges list. In the end, it should have 2 * N * M elements. The direction of the edges should be either 'h' or 'v', depending on the matrix that you parsed.

If you don't use the h and v matrices for any other purposes, you may drop them altogether, since you can compute the weights of the edges directly from the i matrix.

Finally, for the purposes of the algorithm, you need to sort the list using the weight as a criterion:

edges.sort(key=weight)