CODEWITHSUNDEEP
pythonalgorithmsubset
Christian
Christian

Reputation: 577

Algorithm to generate subsets satisfying binary relation

I am looking for a reasonable algorithm in python (well, because I have rather complicated mathematical objects implemented in python, so I cannot change the language) to achieve the following:

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.

In some more detail: Suppose I am given a binary relation on a set of objects, say

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)

I can also assume that the relation bin_rel is reflexive (this is, binary_rel(a,a) is True holds) and symmetric (this is, binary_rel(a,b) is binary_rel(b,a) holds).

I am now given a set X and a function bin_rel as above and seek an efficient algorithm to obtain the desired subsets of X

For example, in the case of the set intersection above (with sets replaced by lists for easier reading):

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

This problem doesn't seem to be very exotic, so most welcome would be a pointer to an efficient existing snippet of code.

Upvotes: 2

Views: 761

Answers (2)

niemmi
niemmi

Reputation: 17263

As Matt Timmermans noted this is finding maximal cliques problem that can be solved by Bron–Kerbosch algorithm. NetworkX has implementation that can be used for Python.

Upvotes: 3

Paul Evans
Paul Evans

Reputation: 27567

If you want to use python straight out of the box, you could use the following as a starting point:

from itertools import combinations

def maximal_compatible_subsets(X, bin_rel):
    retval = []
    for i in range(len(X) + 1, 1, -1):
        for j in combinations(X, i):
            if all(bin_rel(a, b) for a, b in combinations(j, 2)) and not any(set(j).issubset(a) for a in retval):
                retval.append(tuple(j))
    return tuple(retval)

if __name__ == '__main__':
    x = ( (1,2,3), (1,3), (1,6), (3,4), (3,5), (4,5) )

    def nonempty_intersection(a, b):
        return set(a).intersection(b)

    print x
    print maximal_compatible_subsets(x, nonempty_intersection)

Outputs:

((1, 2, 3), (1, 3), (1, 6), (3, 4), (3, 5), (4, 5))
(((1, 2, 3), (1, 3), (3, 4), (3, 5)), ((1, 2, 3), (1, 3), (1, 6)), ((3, 4), (3, 5), (4, 5)))

Upvotes: 0

Related Questions