complete_graph.rb

#!/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