monora/rgl — pull request #5 by KL-7 (2013-01-12 19:45:45+00:00)
Title: Add Dijkstra shortest path algorithm.

Based on the discussion [here](https://groups.google.com/forum/?fromgroups=#!topic/ruby-graph-library/7FdJr4lw8uA) I've created a very basic implementation of the Dijkstra shortest path algorithm.

This pull request is not yet ready for being merged, but I'd like to put it here at least for review, so if you have any concerns or ideas about this feature – let me know.

Things that I'm going to do before merging:
1. Add more specs. Looks like the general flow of the algorithm is working, but I might have missed some special cases. Adding more test cases should help with that.
2. Document public methods. Once the overall API of the feature is accepted, I'll add all necessary comments, so we can have nice docs for Dijkstra algorithm.
3. Add alternative `shortest_paths` method (plural `paths`) to find paths from the source to *all* other vertices of the graph.

I didn't want to spam you, @monora, with a lot of tiny pull requests, so I included some other minor fixes into this one. Among them:
* Extracting `GraphIterator`, `GraphVisitor`, and `GraphWrapper` from `traversal.rb` into separate files so these classes can be used in other features, including Dijkstra algorithm. It shouldn't break any client code, but at least it'll let us use these classes independently.
* Requiring `test_helper` in all test files. It's not critical right now, but usually it's very handy to have a common place for all test helpers.
* Adding `script/test_all` script that runs all tests together and then one by one. It should help us detect missing require statements in the tests and at the same time make sure that we don't have undesired dependencies between them. Locally you can still use `rake test` to run all tests at once, but Travis CI will use this script instead.
* Removing JRuby from `.travis.yml`. I'm not sure about this particular move. The problem is that for Dijkstra algorithm I needed priority queue, so I decided to use [`algorithms`](https://github.com/kanwei/algorithms) gem. It's a very nice library, but for performance reasons it uses C extensions. Current JRuby version with some special options is capable of compiling C extensions in gems, but, as far as I know, they plan to completely remove support for C extensions from the future version of JRuby. That means that if we depend at least on a single gem that uses C extensions (in this case, it's `algorithms` gem), we can't fully support JRuby.
* Removing `require 'rubygems'` from the gem source code. Why it's a good idea is described [here](http://tomayko.com/writings/require-rubygems-antipattern). Though, I left one require statement for `rubygems` in `test_helper`, because it's necessary to run tests on MRI 1.8.7.
* Minor refactoring of `GraphVisitor` module. Just check out the diff to see what was changed. I hope you'll like it.

Please, review this pull request and let me know what you think about it. Meanwhile, I'll continue working on the necessary additions that I listed above.