# 인접 리스트로 구현한 그래프
# 2009.03.16, Jungtaek Lim(Heart)

class ListNode
  attr_accessor :data, :next

end

class LinkedList
  def initialize
    @root = ListNode.new
    @root.next = nil
    
  end

  def add_node(data)
    cur_node = @root.next
    prev_node = @root

    while cur_node != nil
      break if cur_node.data > data

      prev_node = cur_node
      cur_node = cur_node.next
    end

    node = ListNode.new
    node.data = data

    prev_node.next = node
    node.next = cur_node

  end

  def print_node
    cur_node = @root.next

    while cur_node != nil
      print cur_node.data.to_s + " "

      cur_node = cur_node.next
    end

    puts
    
  end
  
end

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

    @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_list[@max_vertex_number] = LinkedList.new

  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_list[tail_index].add_node(head_vertex_name)
    else
      @adjacent_list[tail_index].add_node(head_vertex_name)
      @adjacent_list[head_index].add_node(tail_vertex_name)
    end

    return true
  end

  def print_adjacent_list
    i = 0

    @adjacent_list.each do |adjacent_list_row|
      print @vertex_set[i] + "\t"

      adjacent_list_row.print_node

      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_list

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_list