maetl

Strongly Connected Components in Ruby

I've had a massive pile of code and experiments sitting around for too long. It's time to move on, but I thought, why not throw it out to rot instead of just disposing of it? Who knows, the stuff in this code compost heap might even be useful to someone one day.

Case in point... Here is a digraph manipulator (zip) in iterative Ruby that implements the modified version of Tarjan's algorithm, as explained in the improved algorithm paper by David Pearce. Use it like this:

graph = DigraphManipulator.new(vertex_set, edge_set)
clusters = graph.find_scc()

The usage of set data structures (strangely rare in bread and butter Ruby) leaves a lot to be desired, but the code itself seems malleable enough. If you find a use for it, or spot any mistakes, please let me know.