Storing different algorithms and using them for demonstration

Question

I have an app for creating simple graphs (the kind with vertices and edges) and then using different algorithms on them (BFS, DFS, topsort, Prim's etc) for demonstrating how they work.

I'm now working on porting it into a Rails app and deploying so it can be used by my university (hopefully).

Currently the graphs are stored in a SQLite db and I am planning to do some D3 magic on them.

Then to the real problem, how should I implement and store the algorithms?

I want to be able to "step" through the algorithm, showing step by step how it works on the graph. In my previous implementation, written in Java, I had an abstract Algorithm class with abstract methods like init, step and reset. But, now that we are out of the Java world and using wonderful Ruby, I have a feeling that there's a really clever and elegant way achieving the same.

I am planning to pack it into a Rails engine, just for kicks.

Here is the mentioned Java implementation: https://github.com/7SLEVIN/visualgraphalgs

Answer 1

This sounds like a state machine to me. You've got a graph (V,E) and a current traversal state S (been a while since my algorithms classes but I'm guessing this is a recursive stepping-through of various exploration options) including a handle to your given currently selected strategy (i.e. your graph traversal algorithm).

There's a nice ruby gem called state_machine that could give you the framework you need to move through states like Initial -> In Progress (repeat as needed) -> Completed

The key here will be figuring out a way to - from within the In Progress state - serialize the current details of your traversal so that it can be paused indefinitely while you show it off in the browser and then restarted on demand in order to execute the next step. This is a lot like stepping through breakpoints in a debugger, except you'll likely be implementing a lot of that by hand rather than relying on a real debugger.