class Graph

Attributes

edges[R]
nodes[R]

Public Class Methods

new(edges: {}) click to toggle source
# File lib/developer_cliques/graph.rb, line 6
def initialize edges: {}
  @edges = edges
  @nodes = edges.keys
end

Public Instance Methods

max_cliques() click to toggle source
# File lib/developer_cliques/graph.rb, line 15
def max_cliques
  @cliques ||= []
  bron_kerbosch(possibles: nodes) if @cliques.empty?
  @cliques
end
neighbours(node: @edges[node] || []) click to toggle source
# File lib/developer_cliques/graph.rb, line 11
def neighbours node:
  @edges[node] || []
end

Private Instance Methods

bron_kerbosch(result: [], possibles: [], excluded: []) click to toggle source

Bron-Kerbosch Algorithm with Pivoting @param result is the set with the nodes of a maximal clique @param possibles is the set of the possible nodes to look @param excluded is the set of the excluded nodes

# File lib/developer_cliques/graph.rb, line 30
def bron_kerbosch result: [], possibles: [], excluded: []
  @cliques << result if possibles.empty? and excluded.empty?

  #Pivoting: it takes first element of possibles as pivot
  (possibles - neighbours(node: possibles.first)).each do |n|
    # Recursive call
    bron_kerbosch result: result | [n],
                  possibles: possibles & neighbours(node: n),
                  excluded: excluded & neighbours(node: n)

    possibles -= [n]
    excluded |= [n]
  end
end