# $seen is a hash to memoize prevIoUsly seen sets
# $sparse is a hash of usernames to a list of neighboring usernames
# $set is the list of output clusters
 
$seen = {}
def subgraph(set,adj)
    hash = (set + adj).sort
    return if $seen[hash]
    $sets.push set.sort.join(",") if adj.empty? and set.size > 2
    adj.each {|node| subgraph(set + [node],$sparse[node] & adj)}
    $seen[hash] = true
end
 
$sparse.keys.each do |vertex|
    subgraph([vertex],$sparse[vertex])
end

我的Bron Kerbosch实施：

def bron_kerbosch(set,points,exclude)
    $sets.push set.sort.join(',') if set.size > 2 and exclude.empty? and points.empty?
    points.each_with_index do |vertex,i|
        points[i] = nil
        bron_kerbosch(set + [vertex],points & $sparse[vertex],exclude & $sparse[vertex])
        exclude.push vertex
    end
end
 
bron_kerbosch [],$sparse.keys,[]

我还实现了旋转和简并排序,这减少了bron_kerbosch执行时间,但还不足以超越我的初始解决方案.这种情况似乎是错误的;我错过了什么算法见解？如果您需要查看完整的代码,这里有一个更详细的writeup.我已经在伪随机集上测试了这个,其大小达到了一百万左右.