Skip to content

Instantly share code, notes, and snippets.

@madis
Last active Nov 20, 2016
Embed
What would you like to do?
#!/usr/bin/env ruby
class GraphGenerator
# Returns list of edges for n-vertex complete graph
#
# Example:
# GraphGenerator.generate(4)
# [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]
def self.generate(count)
if count == 1
[[1,1]]
else
vertices = (1...count).to_a # Generate list of edges
graph = vertices.map do |e| # For each vertex
(e..count).map {|other_end| [e, other_end] } # Connect it to every remaining vertex
end.flatten(1) # Bring nested array of edges for each vertex to the same level
graph.reject { |edge| edge.first == edge.last } # Remove duplicate edges (e.g. [2,1] == [1,2])
end
end
end
# Usage:
# puts "4 tipuline t2isgraaf: ", GraphGenerator.generate(4)
describe 'graph generator' do
subject { GraphGenerator.generate(vertex_count) }
context '1 vertex' do
let(:vertex_count) { 1 }
it { should eq [[1, 1]] }
end
context '2 vertices' do
let(:vertex_count) { 2 }
it { should eq [[1, 2]] }
end
context '4 vertices' do
let(:vertex_count) { 4 }
it { should eq [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] }
end
context '100 vertices' do
let(:vertex_count) { 100 }
it 'has correct number of edges' do
expect(subject.count).to eq 100*(100 - 1) / 2
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment