<commit_before>module ArtDecomp class Graph

  def initialize blanket, seps
    vertices = blanket.ints.dup
    vertices.delete_if { |this| vertices.any? { |other| other != this and other & this == this } }
    @edges = Hash[vertices.map { |vertex| [vertex, Set[]] }]
    relevant = Hash[vertices.map { |v| [v, seps.select { |s| v&s != 0 and v&s != s }.to_set] }]
    vertices.pairs.each do |a, b|
      if (relevant[a] & relevant[b]).any? { |s| a&s != b&s }
        @edges[a] << b
        @edges[b] << a
      end
    end
  end

  def adjacent *vertices
    vertices.map { |vertex| @edges[vertex] }.inject(:|) - vertices
  end

  def blanket_from_colouring
    colours = {}
    @edges.keys.sort_by { |vert| [-degree(vert), vert] }.each do |vertex|
      forbidden = adjacent(vertex).map { |vert| colours[vert] }.to_set
      # FIXME: consider selecting colours on the least-popular-first basis
      colour = :a
      colour = colour.next while forbidden.include? colour
      colours[vertex] = colour
    end
    blocks = Hash.new 0
    colours.each { |vertex, colour| blocks[colour] |= vertex }
    Blanket.new blocks.values
  end

  def complete?
    @edges.values.map(&:size).inject(:+) == @edges.keys.size * (@edges.keys.size - 1)
  end

  def degree vertex
    @edges[vertex].size
  end

  def edges
    @edges.map { |v, adjacents| adjacents.map { |adj| Set[v, adj] } }.flatten.to_set
  end

  def merge_by_edge_labels!
    return self if @edges.keys.size == 1
    pins = @edges.keys.size.log2_ceil
    until @edges.keys.size.log2_ceil < pins
      # FIXME: edge labels can/should be cached from previous computations
      a, b = *edges.sort_by { |edge| yield *edge }.first
      merge! a, b
    end
    self
  end

  def merge_by_vertex_degrees!
    pins = @edges.keys.size.log2_ceil
    until @edges.keys.size.log2_ceil < pins or complete?
      a, b = *@edges.keys.sort_by { |v| -degree(v) }.pairs.find { |v1, v2| not @edges[v1].include? v2 }
      merge! a, b
    end
    self
  end

  def merge_until_complete!
    merge_by_vertex_degrees! until complete?
    self
  end

  def vertices
    @edges.keys.to_set
  end

  private

  def merge! a, b
    new = a | b
    adjs = adjacent(a) | adjacent(b)
    adjs.each { |adj| @edges[adj] << new }
    @edges[new] = adjs
    @edges.delete(a).each { |adj| @edges[adj].delete a } unless a == new
    @edges.delete(b).each { |adj| @edges[adj].delete b } unless b == new
  end

end end<commit_msg>Graph: replace @edges.keys.size with @edges.size<commit_after>module ArtDecomp class Graph

  def initialize blanket, seps
    vertices = blanket.ints.dup
    vertices.delete_if { |this| vertices.any? { |other| other != this and other & this == this } }
    @edges = Hash[vertices.map { |vertex| [vertex, Set[]] }]
    relevant = Hash[vertices.map { |v| [v, seps.select { |s| v&s != 0 and v&s != s }.to_set] }]
    vertices.pairs.each do |a, b|
      if (relevant[a] & relevant[b]).any? { |s| a&s != b&s }
        @edges[a] << b
        @edges[b] << a
      end
    end
  end

  def adjacent *vertices
    vertices.map { |vertex| @edges[vertex] }.inject(:|) - vertices
  end

  def blanket_from_colouring
    colours = {}
    @edges.keys.sort_by { |vert| [-degree(vert), vert] }.each do |vertex|
      forbidden = adjacent(vertex).map { |vert| colours[vert] }.to_set
      # FIXME: consider selecting colours on the least-popular-first basis
      colour = :a
      colour = colour.next while forbidden.include? colour
      colours[vertex] = colour
    end
    blocks = Hash.new 0
    colours.each { |vertex, colour| blocks[colour] |= vertex }
    Blanket.new blocks.values
  end

  def complete?
    @edges.values.map(&:size).inject(:+) == @edges.size * (@edges.size - 1)
  end

  def degree vertex
    @edges[vertex].size
  end

  def edges
    @edges.map { |v, adjacents| adjacents.map { |adj| Set[v, adj] } }.flatten.to_set
  end

  def merge_by_edge_labels!
    return self if @edges.size == 1
    pins = @edges.size.log2_ceil
    until @edges.size.log2_ceil < pins
      # FIXME: edge labels can/should be cached from previous computations
      a, b = *edges.sort_by { |edge| yield *edge }.first
      merge! a, b
    end
    self
  end

  def merge_by_vertex_degrees!
    pins = @edges.size.log2_ceil
    until @edges.size.log2_ceil < pins or complete?
      a, b = *@edges.keys.sort_by { |v| -degree(v) }.pairs.find { |v1, v2| not @edges[v1].include? v2 }
      merge! a, b
    end
    self
  end

  def merge_until_complete!
    merge_by_vertex_degrees! until complete?
    self
  end

  def vertices
    @edges.keys.to_set
  end

  private

  def merge! a, b
    new = a | b
    adjs = adjacent(a) | adjacent(b)
    adjs.each { |adj| @edges[adj] << new }
    @edges[new] = adjs
    @edges.delete(a).each { |adj| @edges[adj].delete a } unless a == new
    @edges.delete(b).each { |adj| @edges[adj].delete b } unless b == new
  end

end end
{'fraction_non_alphanumeric': 0.13857142857142857, 'fraction_numerical': 0.004897959183673469, 'mean_word_length': 2.7100681302043905, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1515322', 'n_tokens_mistral': 1784, 'n_tokens_neox': 1747, 'n_words': 473}