dijkstra.rb

# Written by Brad Orego, Dijkstra's implementation adapted from http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Ruby
# Ruby implementation of Dijkstra's algorithm intended to be run in Sonic Pi
# Define a graph with random arc weights, traverse the graph, playing a note for each node, then at the end, play the shortest path
# Repeat for 30 seconds, then stop after that run finishes
Vertex = Struct.new(:name, :neighbours, :dist, :prev)
def init_graph(graph)
  @vertices = Hash.new{|h,k| h[k]=Vertex.new(k,[],Float::INFINITY)}
  @edges = {}
  graph.each do |(v1, v2, dist)|
    @vertices[v1].neighbours << v2
    @vertices[v2].neighbours << v1
    @edges[[v1, v2]] = @edges[[v2, v1]] = dist
  end
  @dijkstra_source = nil
  return @vertices
end
def ext_dijkstra(source)
  count = 0
  return  if @dijkstra_source == source
  q = @vertices.values
  q.each do |v|
    v.dist = Float::INFINITY
    v.prev = nil
  end
  @vertices[source].dist = 0
  until q.empty?
    u = q.min_by {|vertex| vertex.dist}
    break if u.dist == Float::INFINITY
    q.delete(u)
    u.neighbours.each do |v|
      puts v
      with_synth :beep do
        play v
        sleep 0.125
      end
      count += 1
      vv = @vertices[v]
      if q.include?(vv)
        alt = u.dist + @edges[[u.name, v]]
        if alt < vv.dist
          vv.dist = alt
          vv.prev = u.name
        end
      end
    end
  end
  puts count
  @dijkstra_source = source
end

def shortest_path(source, target)
  ext_dijkstra(source)
  path = []
  u = target
  while u
    path.unshift(u)
    u = @vertices[u].prev
  end
  return path, @vertices[target].dist
end

def new_path
  prime = [2, 3, 5, 7, 11, 13, 17, 19, 23]
  use_random_seed Time.now.to_i
  start, stop = :a, :e
  g= init_graph([[:a, :b, prime.choose],
                 [:a, :c, prime.choose],
                 [:a, :f, prime.choose],
                 [:b, :c, prime.choose],
                 [:b, :d, prime.choose],
                 [:c, :d, prime.choose],
                 [:c, :f, prime.choose],
                 [:d, :e, prime.choose],
                 [:e, :f, prime.choose],
                 ])
  return shortest_path(start, stop)
end

define :dijkstra do
  puts "dijkstra"
  path, dist = new_path
  puts path.join(" -> ")

  start = Time.now.to_i
  sleep 0.5
  use_synth :fm
  loop do
    now = Time.now.to_i
    if (path.length == 0)

      if (now - start > 30)
        return
      else
        path, dist = new_path
        puts path.join(" -> ")
        sleep 0.5
      end
    end
    play path.shift, sustain: 2
    sleep 2
  end
  # sleep 4
end


dijkstra