OAKS: Adaptable Kruskal Solver

OAKS: Adaptable Kruskal Solver - 0.1

Matt Windsor (captainhayashi)

Tags:

Description

The name is a misnomer - as of writing, OAKS isn't terribly adaptable, but can solve minimum spanning tree problems both using Kruskal's algorithm and Prim's algorithm.

(A minimum spanning tree problem involves taking a network of points (vertices) connected by lines (edges) which have assigned weights, or numbers representing the work required to traverse said line, and removing high-weighted and unnecessary lines to create a graph of smallest weight which contains no cycles/redundancies).

I'm hoping to expand on the GUI I've written for this project and possibly eventually release it as a separate library. Currently, it is extremely feature-incomplete, but lightweight. This version was written for Python 3, but as the original Computing project was written in Python 2, it shouldn't be terribly hard to downgrade.

Links

Home Page: http://d-linc.co.uk/python
Source: http://d-linc.co.uk/python/oaks/release/oaks-0.1-src.zip
Windows: http://d-linc.co.uk/python/oaks/release/oaks-0.1-win.zip

Screenshot

click to view original size

Releases

OAKS: Adaptable Kruskal Solver - 0.1 - May 25, 2010

Pygame.org account Comments

If you wish to leave a comment with your pygame.org account, please sign in first.

May 26, 2010 3:07pm - Matt Windsor - nickname: (captainhayashi)
I've been experimenting with Python 3's multiprocessing abilities, and currently have the Kruskal algorithm implemented using a separate process communicating with the console base through a communications pipe, pausing itself only when waiting for user input. This seems to be slower than the usual method, and the use of the pipe is a little esoteric at the moment, but hopefully once cleaned up the end result should make the algorithm system a lot cleaner and less contrived to fit the GUI event system. This should be ready in version 0.2, and I hope to have better documentation of the system soon.
May 26, 2010 11:08am - Matt Windsor - nickname: (captainhayashi)
@Donpachi: Thanks! To be honest, I haven't stress-tested this program terribly much, so I'm surprised it's actually working for anyone other than me =P Hopefully, at some point I can rewrite the algorithm modules to be less clumsy and possibly even spin off into separate processes or use an internal Python interpreter instance, so the algorithms look and act much more like they would if there wasn't a GUI to worry about (and thus it would be far easier for someone to write a new algorithm class, without worrying about how to break the algorithm up into steps so it doesn't tie the UI down).
May 26, 2010 2:50am - Donpachi - nickname: (donpachi)
Downgrading mostly consisted of replacing the super() calls. There are some deprecation warnings about division in the math module. It's a pretty neat start, though the library would probably be more useful for me. :) I've been playing around a bit with a Settlers-like economy structure, and voilÃ¡, down from the heavens falls this ready program that can display the flags and roads in a sensible manner, and even count minimum spanning trees. Now only if you had already put A* in it... ;) But it seems trivial to implement into something like this. Though, I have to admit that the economy's complexity is rapidly spinning out of control, so it may never actually work.