class Ccs::Graph
Public Class Methods
new(edges)
click to toggle source
# File lib/conflict/calendars/graph.rb, line 5 def initialize(edges) @edges = edges end
Public Instance Methods
find_maximum_cliques()
click to toggle source
# File lib/conflict/calendars/graph.rb, line 9 def find_maximum_cliques @cliques ||= [] bron_kerbosch(Set.new, nodes, Set.new) if @cliques.empty? @cliques end
Private Instance Methods
bron_kerbosch(re, pe, xe)
click to toggle source
# File lib/conflict/calendars/graph.rb, line 31 def bron_kerbosch(re, pe, xe) @cliques << re if pe.empty? && xe.empty? pe.each do |ve| bron_kerbosch(re | [ve], pe & neighbours[ve], xe & neighbours[ve]) pe -= [ve] xe |= [ve] end end
neighbours()
click to toggle source
# File lib/conflict/calendars/graph.rb, line 22 def neighbours @neighbours ||= nodes.map do |node| node_neighbours = @edges.select { |edge| edge.include? node }.flatten - [node] [node, node_neighbours] end.to_h end
nodes()
click to toggle source
# File lib/conflict/calendars/graph.rb, line 18 def nodes @nodes ||= @edges.flatten.uniq end