monora/rgl — pull request #9 by KL-7 (2013-05-01 15:20:08+00:00)
Title: Prim's algorithm for minimum spanning tree

Hi Horst,

I was away for a while, but now I'm back and ready to keep moving RGL a bit further in terms of functionality.

First, I added `rake yard` task that generates yard docs in the default `doc/` directory.

Second, as we discussed, I implemented [Prim's algorithm](http://en.wikipedia.org/wiki/Prim%27s_algorithm) for finding a minimum spanning tree (MST). As it turned out, BGL's implementation of this algorithm is heavily based on the implementation of Dijkstra's algorithm. I tried to follow the same idea and looks like it worked pretty well.

I'm not sure how familiar you're with Prim's algorithm, but the idea is that we use the Dijkstra's algorithm flow, but instead of computing minimum distance from the source to each vertex we compute the shortest distance between already completed part of the MST and the vertices that are not yet in the tree. This distance is always just a weight of an edge that connects a vertex, that is not in the tree, with one of the vertices of the MST. As the result, all we need to do is to use Dijkstra's algorithm, but override the way it computes distances.

As always, I'll add more docs and specs soon, but first I'd like to discuss few things:

1. Right now `RGL::PrimAlgorithm#minimum_spanning_tree` returns just an array of edges. Should it build and return the MST as an instance of `AdjacencyGraph` class instead? Returning an array is simpler and probably more flexible (you can do lots of things with an array), but returning the tree as a graph object seems more appropriate.

2. While Dijkstra's algorithm can't handle negative edge weights, looks like it's not the case for Prim's algorithm in general. I'll need to check if the fact that our Prim's algorithm implementation relies on the Dijkstra's algorithm makes any difference, but I guess it doesn't. Therefore I'll need to find a way to accept negative weights when `DijkstraAlgorithm` is used inside `PrimAlgorithm`, but still forbid them when it's used elsewhere.

Please, let me know what you think of the implementation and the two points above.