# 인접 행렬로 구현한 그래프
# 2009.03.16, Jungtaek Lim(Heart)

class Graph
  
  def initialize(is_direct)
    @adjacent_matrix = []

    @vertex_set = []
    
    @max_vertex_number = -1

    @is_direct = is_direct
  end

  def add_vertex(vertex_name)
    @max_vertex_number += 1
    
    @vertex_set[@max_vertex_number] = vertex_name

    # 새로운 정점에 대한 간선을 저장할 부분을 초기화
    @adjacent_matrix[@max_vertex_number] = []
    
    (0..@max_vertex_number).each do |i|
      @adjacent_matrix[@max_vertex_number][i] = 0
    end

    # 기존 정점에 대한 간선을 저장하는 부분에 새로운 정점과의 간선을 초기화
    @adjacent_matrix.each do |adjacent_matrix_row|
      adjacent_matrix_row[@max_vertex_number] = 0
    end
  end

  def add_edge(tail_vertex_name, head_vertex_name)
    tail_index = find_vertex(tail_vertex_name)
    head_index = find_vertex(head_vertex_name)

    return false if (tail_index == -1) || (head_index == -1)

    if @is_direct
      @adjacent_matrix[tail_index][head_index] = 1
    else
      @adjacent_matrix[tail_index][head_index] = 1
      @adjacent_matrix[head_index][tail_index] = 1
    end

    return true
  end

  def print_adjacent_matrix
    print "\t"
    
    @vertex_set.each {|vertex_name| print vertex_name + "\t" }
    puts

    i = 0

    @adjacent_matrix.each do |adjacent_matrix_row|
      print @vertex_set[i] + "\t"

      adjacent_matrix_row.each do |num|
        print num.to_s + "\t"
      end

      puts

      i += 1
    end
  end

  private
  def find_vertex(vertex_name)

    (0...@vertex_set.length).each do |i|
      return i if @vertex_set[i] == vertex_name
    end

    return -1
  end

end

graph = Graph.new(false)

graph.add_vertex('A')
graph.add_vertex('B')
graph.add_vertex('C')
graph.add_vertex('D')

graph.add_edge('A', 'B')
graph.add_edge('A', 'D')
graph.add_edge('B', 'D')
graph.add_edge('B', 'C')
graph.add_edge('C', 'D')

graph.print_adjacent_matrix

puts "------------------------"

graph = Graph.new(true)

graph.add_vertex('A')
graph.add_vertex('B')
graph.add_vertex('C')
graph.add_vertex('D')

graph.add_edge('A', 'B')
graph.add_edge('A', 'D')
graph.add_edge('B', 'D')
graph.add_edge('B', 'C')
graph.add_edge('C', 'D')

graph.print_adjacent_matrix