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