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