Largest shared superclass

Is there an easy way to get the "largest shared superclass" in a list of objects? For example, if

class A(object): pass
class B(A): pass
class C(A): pass
class D(B, C): pass
class E(C): pass
class F(D, E): pass

      

and

b = B()
d = D()
e = E()

      

then

gcs(b, e) is A
gcs(d, e) is C
gcs(e, e) is E

      

+3


source to share


3 answers


Based on Martijn's idea, but using a simpler approach, given that time complexity won't be an issue here (thanks to @veedrac for his inputs):

def gcs(*instances):
    classes = [type(x).mro() for x in instances]
    for x in classes[0]:
        if all(x in mro for mro in classes):
            return x

print gcs(b, e)
print gcs(d, e)
print gcs(e, e)

      

Output:



<class '__main__.A'>
<class '__main__.C'>
<class '__main__.E'>

      

A small variation of the above code using sets:

def gcs(*instances):
    mros = (type(ins).mro() for ins in instances)
    mro = next(mros)
    common = set(mro).intersection(*mros)
    return next((x for x in mro if x in common), None)

      

+4


source


This is essentially a simplified problem with a long and generic subsequence; compare the MRO sequences and return the type with the smallest sum of their indices:

def gcs(a, b):
    """Find the common base class between two classes or instances"""
    try:
        a, b = a.mro(), b.mro()
    except AttributeError:
        a, b = type(a).mro(), type(b).mro()
    a_idx, b_idx = {t: i for i, t in enumerate(a)}, {t: i for i, t in enumerate(b)}
    try:
        return min(a_idx.viewkeys() & b_idx.viewkeys(),
                   key=lambda t: a_idx[t] + b_idx[t])
    except ValueError:
        return None

      

This is an O (M + N) algorithm, where M and N are the MRO sizes of both objects. The function can handle both classes and instances.



Demo with your sample objects:

>>> gcs(e, b)
<class '__main__.A'>
>>> gcs(e, d)
<class '__main__.C'>
>>> gcs(e, e)
<class '__main__.E'>

      

+3


source


I think one problem is that you can have more than one largest common superclass - take a class inheritance structure like

AB ---> A
   \ /
    x
   / \
BA ---> B

      

In this case, both A

and B

are legitimate answers to gca([AB, BA])

.

After facing this in my own code, I realized that I needed to revisit the question:

Find the minimum set of common databases shared by the specified list of classes; defined as all classes that 1) are the parent class of everything in the original list and 2) do not have NO subclasses, which are also included in the returned list.

This last requirement takes care of getting only the "closest" class, but handles the case when there are multiple such values.

The following code implements the following:

def minimal_common_bases(classes):
    # pull first class, and start with it bases
    gen = iter(classes)
    cls = next(gen, None)
    if cls is None:
        return set()
    common = set(cls.__mro__)

    # find set of ALL ancestor classes,
    # by intersecting MROs of all specified classes
    for cls in gen:
        common.intersection_update(cls.__mro__)

    # remove any bases which have at least one subclass also in the set,
    # as they aren't part of "minimal" set of common ancestors.
    result = common.copy()
    for cls in common:
        if cls in result:
            result.difference_update(cls.__mro__[1:])

    # return set
    return result

      

  • NOTE. In the py2 section, you need to use inspect.getmro(cls)

    instead cls.__mro__

    .
+1


source







All Articles