algorithm_bron_kerbosch.rb

# Algorithm maxmimal Bron Kerbosch
class Algorithm
  def initialize(graph)
    @graph = graph
  end

  def bron_kerbosch(noder, nodep, nodex)
    return if nodep.nil? || nodex.nil?

    puts ' ' + noder.sort.join(' ') if maximal_clique?(nodep, nodex)

    nodep.dup.each do |vertex|
      r_new = noder.dup
      r_new.push(vertex)

      bron_kerbosch(r_new, interset(nodep, get_neighbors(vertex)), interset(nodex, get_neighbors(vertex)))

      nodep.delete(vertex)
      nodex.push(vertex)
    end
  end

  private

  def interset(node, neighbors)
    return nil if neighbors.nil?

    node.map { |element| (neighbors.include?(element) ? element : nil) }.compact
  end

  def get_neighbors(vertex)
    @graph[vertex]
  end

  def maximal_clique?(nodep, nodex)
    (nodep.length == 0  && nodex.length == 0)
  end
end