Peekaboo

I started working with spanning trees for euclidean distance graphs today. The first think I obviously needed to do was compute the spanning tree. There are MST algorithms in Python, for example in pygraph and networkx . These use their native graph formats, though, which would have meant I'd have to construct a graph from my point set. I didn't see a way on how to do this and set the edge weights without iterating over all edges. That would probably take longer than the computation of the MST, so I decided to do my own small implementation using numpy. This is an instantiation of Prim's algorithm based on numpy matrices. The input is a dense matrix of distances, the output a list of edges. It is not as pretty as I would have hoped but still reasonably short. If any one has suggestions how to make this prettier, I'd love that. [edit] Using line_profiler I had a quick look a the code and made some minor improvements. It's now significantly faster than net...

[edit] Nowadays you can find  much better implementations of this over at scikit-image. [/edit] Recently I started playing with CRFs on superpixels for image segmentation. While doing this I noticed that Python has very little methods for morphological operations on images. For example I did not find any functions to exctract connected components inside images. For CRFs one obviously needs the superpixel neighbourhood graph to work on and I didn't find any ready made function to obtain it. After some pondering, I came up with something. Since I didn't find anything else online I thought I'd share it. def make_graph(grid): # get unique labels vertices = np.unique(grid) # map unique labels to [1,...,num_labels] reverse_dict = dict(zip(vertices,np.arange(len(vertices)))) grid = np.array([reverse_dict[x] for x in grid.flat]).reshape(grid.shape) # create edges down = np.c_[grid[:-1, :].ravel(), grid[1:, :].ravel()] right = np.c_[grid...