Posts

Showing posts from February, 2012

Simplistic Minimum Spanning Tree in Numpy [update]

Image
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 networkx and al…

Changing Python search path - for good. Or: the magic of the 'site' package.

After using Python for about two years now and being a somewhat active developer, I still frequently run into problems with my Python search path.
Luckily, I usually have root on the boxes I work on, so I could do some hacks.

At the moment, I'm at the IST Austria, where I can use the cluster, but I don't have root. So this time I needed a real solution.

Here it goes:
The problem is the following: I have some locally installed packages, like scikit-learn and joblib, that are not globally installed. That would be easy enough to solve by setting the PYTHONPATH environment variable in my .profile, pointing to the install location.

But I also have newer versions of already installed packages, like IPython. Here, modifying the Python path environment variable doesn't help, as this is appended to the search path. A somewhat hacky solution is to insert your package dir into the search path at the beginning of each script, like so:
import sys sys.path.insert(0, "MYPATH") …