Animated Implementation of Prim's Algorithm in Ruby + JS/Canvas

prim_graph.rb

# R. Scott Reis - Implementation of Prim's Algorithm
# http://en.wikipedia.org/wiki/Prim%27s_algorithm

require 'sinatra'
require 'haml'
require 'json'

module Prim
  class << self
    def get_graph
      nodes = 10.times.inject([]) do |nodes|
        nodes << [rand(0..100), rand(0..100)]
        nodes
      end

      connections = []
      connect_nodes = nodes.clone
      while connect_nodes.length > 1 do
        start_node = connect_nodes.shift
        connect_nodes.each do |end_node|
          connections << {
              start: start_node,
              end:   end_node,
              cost:  Math.hypot(start_node.first - end_node.first,
                                start_node.last - end_node.last)
          }
        end
      end

      graph = { nodes: [nodes.sample], connections: [] }

      while (unconnected_nodes = nodes - graph[:nodes]).length > 0 do
        connect = (connections - graph[:connections]).select do |connect|
          connect_nodes = [connect[:start], connect[:end]]
          (connect_nodes & graph[:nodes]).length > 0 && (connect_nodes & unconnected_nodes).length > 0
        end.min_by do |connect|
          connect[:cost]
        end
        graph[:connections] << connect
        graph[:nodes] = graph[:nodes] | [connect[:start], connect[:end]]
      end

      graph
    end
  end
end

get '/' do
  haml :index
end

get '/graph' do
  content_type :json
  Prim.get_graph.to_json
end

__END__

@@index
!!!
%html
  %head
    %title Prim's Algorithm
  %body
    %h1 Prim's Algorithm
    %canvas{ id: 'canvas', width: 300, height: 300, style: 'margin: 20px;' }
    %script{ type: 'text/javascript', src: 'https://code.jquery.com/jquery-2.1.3.min.js' }
    :javascript
      $(function() {
        var multiplier = 3;
        var canvas = document.getElementById('canvas');
        var ctx = canvas.getContext('2d');
        var i = 0;
        var interval;

        $.get('/graph', function(data) {
          data.nodes.forEach(function(node) {
            ctx.beginPath();
            ctx.arc(node[0] * multiplier, node[1] * multiplier, 2, 0, 2*Math.PI);
            ctx.fill();
          });

          interval = setInterval(function() {
            var connection = data.connections[i];
            var start = connection.start;
            var end = connection.end;
            ctx.beginPath();
            ctx.moveTo(start[0] * multiplier, start[1] * multiplier);
            ctx.lineTo(end[0] * multiplier, end[1] * multiplier);
            ctx.stroke();
            i == data.connections.length - 1 ? clearInterval(interval) : i++;
          }, 200);
        });
      });