python - 生成满足二元关系的子集的算法

Question

我正在 python 中寻找一个合理的算法(好吧，因为我有相当复杂的数学对象在 python 中实现，所以我不能改变语言)来实现以下目标:

I am given a reflexive, symmetric binary relation bin_rel on a set X. The requested function maximal_compatible_subsets(X, bin_rel) should return all containmentwise maximal subsets of X such that the binary relation holds for all pairs a,b of elements in X.

更详细一点:假设我得到了一组对象的二元关系，比如说

def bin_rel(elt1,elt2):
    # return True if elt1 and elt2 satisfy the relation and False otherwise
    # Example: set intersection, in this case, elt1 and elt2 are sets
    # and the relation picks those pairs that have a nonempty intersection
    return elt1.intersection(elt2)

我还可以假设关系 bin_rel 是自反(即 binary_rel(a,a) 为 True 成立)并且 < strong>对称(即 binary_rel(a,b) 是 binary_rel(b,a) 成立)。

我现在得到一个集合 X 和一个函数 bin_rel ，并寻求一种有效的算法来获得所需的 X 子集>/p>

例如，在上面的集合交集的情况下(集合被列表替换以便于阅读):

> X = [ [1,2,3], [1,3], [1,6], [3,4], [3,5], [4,5] ]
> maximal_compatible_subsets(X,bin_rel)
[[[1,2,3],[1,3],[1,6]], [[1,2,3],[1,3],[3,4],[3,5]], [[3,4],[3,5],[4,5]]]

这个问题似乎不是很奇特，所以最受欢迎的是指向有效的现有代码片段的指针。

Answer 1

正如 Matt Timmermans 指出的那样，这是 finding maximal cliques problem可以通过 Bron–Kerbosch algorithm 解决.NetworkX 有 implementation可用于 Python。