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) is True成立)并且<强>对称(即binary_rel(a,b) 是binary_rel(b,a) 成立)。

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

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

> 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。