monora/rgl — pull request #7 by KL-7 (2013-02-18 18:15:30+00:00)
Title: Bellman-Ford shortest paths algorithm

I've prepared an implementation of Bellman-Ford shortest paths algorithm.

It's **not yet finished**: I need at least to add more tests and, probably, make some minor tweaks, but in general I'm pretty happy with the result.

I tried to extract as many parts of the Dijkstra algorithm implementation as possible, and in my opinion it worked out very well. I decided to put `:nodoc:` on utility `EdgeWeightsMap` and `PathBuilder` class, because I don't expect them to be very useful outside of the gem (at least not in their current state).

Few things to note:

1. I didn't add a method for finding the shortest path from a source to a single target since Bellman-Ford finds all paths anyway.
2. By default, if there's a negative-weight cycle (one of the edges is not completely relaxed after the iterations are finished), it raises an exception. This behavior can be overridden by setting custom `edge_not_minimized` event handler.
3. Looks like `each_edge` for an undirected graph yields each edge only once, so I had to add a little hack to relax undirected edges in both directions.

@monora, I'd appreciate any review or advice and will try to add more tests and finish the feature in the next few days.

One more idea that I'll probably try is extracting a common base class `ShortestPathVisitor` and derive both `DijkstraVisitor` and `BellmanFordVisitor` from it to make this hierarchy a bit more symmetric. That will also allow to leave `color_map` initialization only in Dijkstra visitor (we don't need colors for Bellman-Ford anyway).