# This is a very simple hash based graph utility class.
# By Mykl Clason
class Graph
  def self.undirected_graph_from_edges(edges)
    # Edges are (a,b) pairs with a => b and b => a relationships.
    graph = {}
    edges.each do |source, adjacency|
      graph[source] = Set.new unless graph[source].present?
      graph[adjacency] = Set.new unless graph[adjacency].present?
      graph[source].add(adjacency)
      graph[adjacency].add(source)
    end

    graph
  end

  def self.directed_graph_from_edges(edges)
    # Edges are (a,b) pairs with a => b relationships.
    graph = {}
    edges.each do |source, adjacency|
      graph[source] = Set.new unless graph[source].present?
      graph[source].add(adjacency)
    end

    graph
  end

  def self.invert(graph)
    # Reverses direction of graph
    edges = []
    graph.each do |node, adjacencies|
      adjacencies.each do |adjacency|
        edges.push [adjacency, node]
      end
    end

    directed_graph_from_edges(edges)
  end

  def self.diff(graph, subgraph)
    # Generates a new graph that is graph - subgraph
    new_graph =  graph.deep_dup
    subgraph.each do |node, connections|
      new_graph[node] = new_graph[node] - connections if new_graph[node].present?
      new_graph.delete(node) unless new_graph[node].present?
    end

    new_graph
  end

  def self.intersect(primary_graph, secondary_graph)
    # Generates a new graph that is primary_graph | secondary_graph
    new_graph =  {}
    nodes = (primary_graph.keys + secondary_graph.keys).uniq
    nodes.each do |node|
      node_intersect = (primary_graph[node] || Set.new) & (secondary_graph[node] || Set.new)
      new_graph[node] = node_intersect if node_intersect.present?
    end

    new_graph
  end

  def self.union(primary_graph, secondary_graph)
    # Generates a new graph that is primary_graph & secondary_graph
    new_graph =  {}
    nodes = (primary_graph.keys + secondary_graph.keys).uniq
    nodes.each do |node|
      new_graph[node] = (primary_graph[node] || Set.new) | (secondary_graph[node] || Set.new)
    end

    new_graph
  end

  def self.adjacency_counter_hash(graph)
    # Generates a hash of the counts of the adjacencies
    hash_counter = {}
    graph.values.map(&:size).each do |size|
      hash_counter[size] = (hash_counter[size] || 0) + 1
    end

    hash_counter
  end

  def self.adjacency_size_map(graph)
    graph.map { |node, adjacencies| [node, adjacencies.size]  }.to_h
  end

  def self.adjacency_counts(graph)
    graph.values.map(&:size)
  end

  def self.size(graph)
    graph_vertex_sizes(graph).sum
  end

  def self.vertex_subset(graph, vertex_set)
    # Creates a subset of the graph that contains only the vertex set
    vertex_set = vertex_set.to_set

    new_graph = {}
    vertex_set.each do |vertex|
      connections = graph[vertex]
      next unless connections.present?
      connections = (graph[vertex] || Set.new) & vertex_set
      new_graph[vertex] = connections if connections.present?
    end

    new_graph
  end
end