TSort implements topological sorting using Tarjan's algorithm for strongly connected components.
TSort is designed to be able to be used with any object which can be interpreted as a directed graph.
TSort requires two methods to interpret an object as a graph,
tsort_each_node and tsort_each_child.
tsort_each_nodeis used to iterate for all nodes over a graph.tsort_each_childis used to iterate for child nodes of a given node.
The equality of nodes are defined by eql? and hash since TSort uses Hash internally.
Add this line to your application's Gemfile:
gem'tsort'And then execute:
$ bundle install
Or install it yourself as:
$ gem install tsort
The following example demonstrates how to mix the TSort module into an
existing class (in this case, Hash). Here, we're treating each key in
the hash as a node in the graph, and so we simply alias the required
#tsort_each_node method to Hash's #each_key method. For each key in the
hash, the associated value is an array of the node's child nodes. This
choice in turn leads to our implementation of the required #tsort_each_child
method, which fetches the array of child nodes and then iterates over that
array using the user-supplied block.
require'tsort'classHashincludeTSortaliastsort_each_nodeeach_keydeftsort_each_child(node, &block)fetch(node).each(&block)endend{1=>[2,3],2=>[3],3=>[],4=>[]}.tsort#=> [3, 2, 1, 4]{1=>[2],2=>[3,4],3=>[2],4=>[]}.strongly_connected_components#=> [[4], [2, 3], [1]]After checking out the repo, run bin/setup to install dependencies. Then, run rake test to run the tests. You can also run bin/console for an interactive prompt that will allow you to experiment.
To install this gem onto your local machine, run bundle exec rake install. To release a new version, update the version number in version.rb, and then run bundle exec rake release, which will create a git tag for the version, push git commits and tags, and push the .gem file to rubygems.org.
Bug reports and pull requests are welcome on GitHub at https://github.com/ruby/tsort.