A common problem posed in coding competitions and undergraduate computer science classes is implementing an algorithm for finding the shortest path through a series of interconnected nodes. It can be phrased in many ways, mostly because graph theory (which is the domain of this particular problem) applies to so many areas of life. Things like driving directions, routing packets in a network, shipping logistics, and so many NP problems are examples of the same problem. It turns out that finding the shortest/lowest cost path through a graph is difficult. While Edsger Dijkstra wrote his famous algorithm to solve this problem back in 1956, there aren’t many libraries to actually use it, at least not for Ruby and in a practical sense. Sure, there are plenty of academic demonstrations but I couldn’t find anything that I would want to depend on as a library (it turns out that rgl is pretty great). This inspired me to write connected, which can be used to search weighted, directed, or undirected graphs.
With Connected, it’s possible to write simple demonstrations or even write “real” code by subclassing the included Connected::GenericNode, Connected::GenericConnection, and Connected::Path classes. I demonstrate this in the simple use-cases section of the README. The real power of the library, however, comes from the Connected::Vertex and Connected::Edge modules which can be mixed into arbitrary Ruby classes (or other modules). This means you can extend plain old Ruby objects, ActiveRecord models, or anything that can be represented by a graph.
If you have an object (or collection of related objects) that are Vertex-like (meaning they’re the things that are connected) and you can figure out a way to represent connections between those objects — either dynamically or through other objects — you can use Connected to find optimal routes between them. I demonstrate this in the README with an very lightweight version of OSPF on some simple network-related classes. I also demonstrate it with a driving directions example in the rspec tests in the library itself.
This was a fun project to write and I plan on continuing to expand it by adding more capabilities and graph theory-related helper functions.
While this was a ton of fun to write and I will probably continue adding to it, I’m sad that I just now found rgl: https://github.com/monora/rgl
Being that it is based on Boost (the C++ library), it will be faster than I could ever hope to make Connected, plus it offers tons more features. I definitely recommend using rgl instead of Connected.