Add Dijkstra shortest path algorithm.

[KL-7]

Based on the discussion here 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 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. 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.

[KL-7]

I added a few commits with shortest_paths implementation, more comments, and visitor test. Now I'm pretty much satisfied with the result. The only thing that worries me a bit is that test graph is quite trivial, but I'm not sure how to build a better test case without making it too big and complicated.

@monora, let me know what you think about the result. If everything looks fine – feel free to merge. When it's done I'd be glad to hear any thoughts on what is the best feature to start next. Meanwhile, I'll explore BGL myself and see what basic features RGL lacks.

[monora]

Kirill Lashuk notifications@github.com writes:

I added a few commits with shortest_paths implementation, more comments, and
visitor test. Now I'm pretty much satisfied with the result. The only thing that
worries me a bit is that test graph is quite trivial, but I'm not sure how to
build a better test case without making it too big and complicated.

Nice. Concerning the tests: Perhaps you could also have a look at
clojures graph lib and eventually translate the dijkstra test cases to
ruby (see
https://github.com/jkk/loom/blob/master/test/loom/test/alg.clj). I am
currently looking into it, because I want to learn clojure now.

@monora, let me know what you think about the result. If everything looks fine –
feel free to merge. When it's done I'd be glad to hear any thoughts on what is
the best feature to start next. Meanwhile, I'll explore BGL myself and see what
basic features RGL lacks.

I just merged. I think BGL has lots of features left to add. I have
currently no priorities to propose.

Horst

[KL-7]

I think I'll add Bellman-Ford algorithm algorithm next as a replacement of Dijkstra algorithm for graphs with negative edge weights. Besides, Dijkstra algorithm implementation should probably raise an exception if a graph with negative edge weights is passed, because most likely it wouldn't return correct result for such graphs anyway. Do you think it's a good idea?

After Bellman-Ford algorithm I'm going to add at least one minimum spanning tree algorithm – either Kruskal's or Prim's. I don't really remember which one is better or when you would use one or another, so I'll need to investigate both of them to refresh my memory.

[monora]

Kirill Lashuk notifications@github.com writes:

I think I'll add Bellman-Ford algorithm algorithm next as a replacement of
Dijkstra algorithm for graphs with negative edge weights. Besides, Dijkstra
algorithm implementation should probably raise an exception if a graph with
negative edge weights is passed, because most likely it wouldn't return correct
result for such graphs anyway. Do you think it's a good idea?
Yes, "Fail fast" is a good practice!

After Bellman-Ford algorithm I'm going to add at least one minimum spanning tree
algorithm – either Kruskal's or Prim's. I don't really remember which one is
better or when you would use one or another, so I'll need to investigate both of
them to refresh my memory.
Sounds good!

Horst