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.  Using line_profiler I had a quick look a the code and made some minor improvements. It's now significantly faster than net
Showing posts from February, 2012
- Other Apps
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, "