Algorithm to generate subsets satisfying binary relation

Question

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.

The intersection was just a simple example. In general, I am given bin_rel, so I do not worry how this code is written. Also, I can assume it to be reflexive and symmetric, and I do not need to test that. But this assumption will certainly influence the algorithm as I do not ever need to test bin_rel(a,a) or (both bin_rel(a,b) and bin_rel(b,a)). — Christian
– Christian, Commented Nov 4, 2016 at 12:21
Note that this is NP-hard, since you can use it to solve max-clique: en.wikipedia.org/wiki/Clique_problem — Matt Timmermans
– Matt Timmermans, Commented Nov 4, 2016 at 12:23
@MattTimmermans: Now as you write this, indeed what that algorithm searches for is exactly the set of all maximal cliques (or maximal independent sets) in a graph. — Christian
– Christian, Commented Nov 4, 2016 at 12:29

niemmi · Accepted Answer · 2016-11-04 14:03:35Z

3

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.

edited Nov 4, 2016 at 14:03

answered Nov 4, 2016 at 12:39

niemmi

17.3k7 gold badges38 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Christian Over a year ago

Note that it is not the maximal clique problem, as there only one clique (of globally maximal size) is requested, while I was requesting all maximal cliques. Anyway, thanks, and networkx.find_cliques does exactly that.

niemmi Over a year ago

@ChristianStump: Sorry if I was unclear, I reworded the answer a bit to make it clearer. Finding maximal cliques is indeed different problem than finding maximum clique.

Paul Evans · Accepted Answer · 2016-11-04 13:27:11Z

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

Collectives™ on Stack Overflow

Algorithm to generate subsets satisfying binary relation

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related