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.

What's wrong with storing the arrays as-is? Could you explain the shortcoming you're having so that we can try to find a solution that addresses it? — templatetypedef
consider using networkx. networkx.lanl.gov/_modules/networkx/algorithms/mst.html. but to your question you can implement your container as a tuple (source, dest, cost) or class, dict, namedtuple.... Then sort the list of these by cost and add to your union find data structure (make sure to use path compression and union by rank) once source, dest do not have the same representative — jassinm

Spatarel Spatarel · Accepted Answer · 2013-02-01T23:32:59

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)

Implementing Kruskal's Algorithm in Python on images

1 Answers