简而言之,我的幼稚代码(在 Ruby 中)看起来像:
# $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 的执行时间,但不足以超越我最初的解决方案。情况似乎是错误的;我缺少什么算法洞察力?如果您需要查看完整的工作代码,这里有一个更详细的文章。我已经在大小达到一百万左右的伪随机集上对此进行了测试。