class Graph

# File lib/graphify/graph.rb, line 6
def initialize(args)
  @graph =  if args[:storage_type] == 'matrix'
              GraphMatrix.new(args)
            elsif args[:storage_type] == 'list'
              GraphList.new(args)
            end
  @type = args[:type] == 'directed' ? :digraph : :graph
  @name = args[:name]
  @storage_type = args[:storage_type]
end

# File lib/graphify/graph.rb, line 24
def dfs_tree(vertex)
  g = initialize_g
  dfs_helper(vertex, [], g)
  g
end

# File lib/graphify/graph.rb, line 34
def dfs_tree_picture(vertex)
  tree = dfs_tree(vertex)
  if @storage_type == 'matrix'
    produce_picture_from_matrix(tree, '_dfs_tree.png')
  elsif @storage_type == 'list'
    produce_picture_from_list(tree, '_dfs_tree.png')
  end
end

# File lib/graphify/graph.rb, line 30
def edges
  @graph.edges_with_weights
end

# File lib/graphify/graph.rb, line 85
def mst_edges
  kruskals_edges
end

# File lib/graphify/graph.rb, line 78
def mst_picture
  g = GraphViz.new(:G, type: @type)
  picture_vertices = add_vertices_to_picture(g)
  add_mst_edges(picture_vertices, g)
  g.output(png: @name + '_minimum_spanning_tree.png')
end

# File lib/graphify/graph.rb, line 17
def picture
  g = GraphViz.new(:G, type: @type)
  vertices = add_vertices_to_picture(g)
  add_edges_to_picture(vertices, g)
  g.output(png: @name + '.png')
end

# File lib/graphify/graph.rb, line 63
def scc_edge_set
  construct_scc_edges(scc_vertex_sets)
end

# File lib/graphify/graph.rb, line 67
def scc_picture
  g = GraphViz.new(:G, type: @type)
  picture_vertices = add_scc_vertices(scc_vertex_sets, g)
  add_scc_edges(picture_vertices, scc_edge_set, g)
  g.output(png: @name + '_strongly_connected_components.png')
end

# File lib/graphify/graph.rb, line 59
def scc_vertex_sets
  scc_vertex_sets_helper
end

# File lib/graphify/graph.rb, line 43
def shortest_path_tree(vertex)
  g = initialize_g
  distances, predecessors = initialize_djikstras(vertex)
  djikstras_helper(vertex, [], distances, predecessors, g)
  g
end

# File lib/graphify/graph.rb, line 50
def shortest_path_tree_picture(vertex)
  tree = shortest_path_tree(vertex)
  if @storage_type == 'matrix'
    produce_picture_from_matrix(tree, '_shortest_path_tree.png')
  elsif @storage_type == 'list'
    produce_picture_from_list(tree, '_shortest_path_tree.png')
  end
end

# File lib/graphify/graph.rb, line 74
def topological_sort
  scc_total_ordering
end

# File lib/graphify/graph.rb, line 263
def add_edges_to_picture(vertices, g)
  @graph.edges_with_weights.each do |edge|
    picture_edge = g.add_edges(vertices[edge[0]], vertices[edge[1]])
    picture_edge[label: edge[2].to_s]
  end
end

# File lib/graphify/graph.rb, line 148
def add_matrix_edge_to_picture(from, to, edges, vertices, picture)
  return if edges[from][to] == nil
  picture_edge = picture.add_edges(vertices[from], vertices[to])
  picture_edge[label: edges[from][to].to_s]
end

# File lib/graphify/graph.rb, line 243
def add_mst_edges(vertices, g)
  kruskals_edges.each do |edge|
    picture_edge = g.add_edges(vertices[edge[0]], vertices[edge[1]])
    picture_edge[label: edge[2].to_s]
  end
end

# File lib/graphify/graph.rb, line 143
def add_predecessor(from, to, g)
  return if to == from
  g[from][to] = @graph.get_edge_weight(from, to)
end

# File lib/graphify/graph.rb, line 215
def add_scc_edges(scc_picture_vertices, scc_edge_set, g)
  (0..scc_edge_set.size - 1).each do |from|
    (0..scc_edge_set.size - 1).each do |to|
      g.add_edges(scc_picture_vertices[from], scc_picture_vertices[to]) unless scc_edge_set[from][to].nil?
    end
  end
end

# File lib/graphify/graph.rb, line 207
def add_scc_vertices(scc_vertex_set, g)
  vertices = {}
  scc_vertex_set.each do |key, value|
    vertices[key] = g.add_nodes(value.reduce('') { |memo, vertex| memo + vertex.to_s + ', ' })
  end
  vertices
end

# File lib/graphify/graph.rb, line 255
def add_vertices_to_picture(g)
  vertices = {}
  @graph.vertices.each do |vertex|
    vertices[vertex] = g.add_nodes(vertex.to_s)
  end
  vertices
end

# File lib/graphify/graph.rb, line 196
def construct_scc_edges(scc_vertex_set)
  edges = Array.new(scc_vertex_set.size) { Array.new(scc_vertex_set.size) }
  @graph.edges_with_weights.each do |edge|
    from = (scc_vertex_set.select { |k, value| value.include?(edge[0]) }).keys[0]
    to = (scc_vertex_set.select { |k , value| value.include?(edge[1]) }).keys[0]
    next if to == from || !edges[from][to].nil?
    edges[from][to] = 1
  end
  edges
end

# File lib/graphify/graph.rb, line 108
def dfs_helper(vertex, seen, g)
  seen << vertex
  @graph.get_out_edges(vertex).each do |neighbour|
    next if seen.include?(neighbour)
    g[vertex][neighbour] = @graph.get_edge_weight(vertex, neighbour)
    dfs_helper(neighbour, seen, g)
  end
end

# File lib/graphify/graph.rb, line 130
def djikstras_helper(vertex, seen, current_d, predecessors, g)
  seen << vertex
  add_predecessor(predecessors[vertex], vertex, g)
  @graph.get_out_edges(vertex).each do |node|
    next if seen.include?(node) || current_d[vertex] + @graph.get_edge_weight(vertex, node) > current_d[node]
    current_d[node] = current_d[vertex] + @graph.get_edge_weight(vertex, node)
    predecessors[node] = vertex
  end
  current_d.delete(vertex)
  return if seen.size == predecessors.keys.size
  djikstras_helper(current_d.key(current_d.values.min), seen, current_d, predecessors, g)
end

# File lib/graphify/graph.rb, line 119
def initialize_djikstras(start)
  dist = {}
  predecessors = {}
  @graph.vertices.each do |vertex|
    dist[vertex] = vertex == start ? 0 : Float::INFINITY
    predecessors[vertex] = vertex == start ? start : nil
  end
  return dist, predecessors
end

# File lib/graphify/graph.rb, line 95
def initialize_g
  num_vertices = @graph.vertices.size
  return Array.new(num_vertices) { Array.new(num_vertices) } if @storage_type == 'matrix'
  g = {}
  (0..num_vertices - 1).each do |num|
    g[num] = {}
  end
  g
end

# File lib/graphify/graph.rb, line 228
def kruskals_edges
  num_vertices = @graph.vertices.size
  sorted_edges = @graph.edges_with_weights.sort_by { |elem| elem[2] }
  result = []
  tree = []
  sorted_edges.each do |edge|
    break if tree.size == num_vertices
    next if tree.include?(edge[0]) && tree.include?(edge[1])
    tree << edge[0] unless tree.include?(edge[0])
    tree << edge[1] unless tree.include?(edge[1])
    result << edge
  end
  result
end

# File lib/graphify/graph.rb, line 281
def produce_picture_from_list(edges, type_name)
  picture = GraphViz.new(:G, type: @type)
  vertices = add_vertices_to_picture(picture)
  edges.keys.each do |key|
    edges[key].keys.each do |s_key|

      picture_edge = picture.add_edges(vertices[key], vertices[s_key])
      picture_edge[label: edges[key][s_key].to_s]
    end
  end
  picture.output(png: @name + type_name)
end

# File lib/graphify/graph.rb, line 270
def produce_picture_from_matrix(edges, type_name)
  picture = GraphViz.new(:G, type: @type)
  vertices = add_vertices_to_picture(picture)
  (0..vertices.size - 1).each do |from|
    (0..vertices.size - 1).each do |to|
      add_matrix_edge_to_picture(from, to, edges, vertices, picture)
    end
  end
  picture.output(png: @name + type_name)
end

# File lib/graphify/graph.rb, line 158
def scc_get_dfs_order(vertex, seen, finished)
  seen << vertex
  @graph.get_out_edges(vertex).each do |neighbour|
    next if seen.include?(neighbour) || finished.include?(neighbour)
    scc_get_dfs_order(neighbour, seen, finished)
  end
  finished.unshift(vertex)
end

# File lib/graphify/graph.rb, line 175
def scc_total_ordering
  finished = []
  for i in (0.. @graph.vertices.size - 1)
    scc_get_dfs_order(i, [], finished) unless finished.include?(i)
  end
  finished
end

# File lib/graphify/graph.rb, line 167
def scc_transpose_dfs(vertex, seen, this_set)
  seen << vertex unless seen.include?(vertex)
  this_set << vertex unless this_set.include?(vertex)
  @graph.get_in_edges(vertex).each do |neighbour|
    scc_transpose_dfs(neighbour, seen, this_set) unless seen.include?(neighbour) || this_set.include?(neighbour)
  end
end

# File lib/graphify/graph.rb, line 183
def scc_vertex_sets_helper
  dfs_sets, seen, counter = {}, [], 0
  scc_total_ordering.each do |vertex|
    next if seen.include?(vertex)
    dfs_set = []
    scc_transpose_dfs(vertex, seen, dfs_set)
    dfs_sets[counter] = dfs_set
    counter += 1
  end
  dfs_sets
end