gistfile1.txt

# Exercise Hash and Set (which is also Hash) insertion and lookup performance.
# Creates a graph with an adjacency map. Finds the connected subgraph from a
# root node, using an Array work list and a visited Set.

require 'set'

size = 100_000

class Node
end

nodes = []

size.times do
  nodes << Node.new
end

adjacency = {}

nodes.each do |node|
  adjacency[node] = nodes.sample(3)
end

def connected(adjacency, root_node)
  visited = Set.new
  to_visit = [root_node]

  while node = to_visit.shift
    unless visited.member? node
      visited.add node
      to_visit.concat adjacency[node].to_a
    end
  end

  visited
end

root_node = nodes.sample

loop do
  start = Time.now

  connected(adjacency, root_node)

  puts Time.now - start
end