Graph Adjacency Matrix Generator

graphgen.rb

# Adjacency Matrix graph generator
# for http://www.reddit.com/r/dailyprogrammer/comments/287jxh/

def input(q)
  print q
  $stdout.flush
  gets.chomp
end

def rand_point
  [rand, rand]
end

def dist(u, v)
  Math.sqrt((v.first - u.first) ** 2 + (v.last - u.last) ** 2)
end

alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

puts 'Note: minimum and maximum connections may not be exact.'

settings = {}
settings[:min_weight] = input('Enter min weight: ').to_i
settings[:max_weight] = input('Enter max weight: ').to_i
settings[:vert_count] = input('Enter number of vertices: ').to_i
settings[:min_cons] = input('Enter min connections per vertex: ').to_i
settings[:max_cons] = input('Enter max connections per vertex: ').to_i
settings[:separator] = ','
settings[:no_edge] = -1

adjacency = Array.new(settings[:vert_count]) { Array.new(settings[:vert_count], settings[:no_edge]) }
vert_position = Array.new(settings[:vert_count]) { rand_point }

edges = 0

(0...settings[:vert_count]).each do |v|
  pre_cons = adjacency[v].select {|w| w != settings[:no_edge]}.length
  puts "Now on #{alphabet[v]}; already connected to #{pre_cons} verts."
  cons = rand(settings[:min_cons]..settings[:max_cons]) - pre_cons
  (puts 'Fully connected, skipping...'; next) if cons <= 0
  connected = (0...settings[:vert_count])
    .reject {|w| v == w}
    .reject {|w| adjacency[v][w] != settings[:no_edge]}
    .reject {|w| adjacency[w].select {|w| w != settings[:no_edge]}.length >= settings[:max_cons]}
    .sort {|w, x| dist(vert_position[v], vert_position[w]) <=> dist(vert_position[v], vert_position[x])}
    .take cons
  puts "Connecting to #{connected.map {|w| alphabet[w]}.join ', '} (#{connected.length})"
  connected.each do |w|
    adjacency[v][w] = rand(settings[:min_weight]..settings[:max_weight])
    adjacency[w][v] = adjacency[v][w]
    edges += 1
  end
end

puts "Finished! Created #{edges} edges.\n"
puts "Unknown output mode #{settings[:mode]}, defaulting to :adjacency." if settings[:mode] != :adjacency
puts settings[:vert_count]
adjacency.each do |col|
  puts col.join settings[:separator]
end

Allocates each vertex a point in 2D space (0<=n<=1) and only connects vertices to relatively near ones so edges don't go all over the place.