java - Finding the nearest common superclass (or superinterface) of a collection of classes

Question

Given a collection of classes, what's the best way to find the nearest common superclass?

E.g., given the following:

interface A {}
interface B {}
interface AB extends A, B {}
interface C {}
class AImpl implements A {}
class ABImpl implements AB {}
class ABImpl2 implements A, B {}
class BCImpl implements B, C {}

I would expect the following (not exhaustive):

commonSuperclass(A, AImpl) == A
commonSuperclass(A, B, C) == Object or null, I'm not picky
commonSuperclass(A, AB) == A
commonSuperclass(AImpl, ABImpl) == A
commonSuperclass(ABImpl, ABImpl2) == either A or B or both, I'm not picky
commonSuperclass(AImpl, ABImpl, ABImpl2) == A
commonSuperclass(ABImpl, ABImpl2, BCImpl) == B
commonSuperclass(AImpl, ABImpl, ABImpl2, BCImpl) == Object

I imagine I could eventually work this out, but someone must have solved it already for things like the type inference in Arrays.asList(...). Can anyone point me to an algorithm, or better yet, some existing utility code?

---

ETA: I know about the reflection APIs. It's the algorithm (or an implementation of such an algorithm) I'm looking for.

ETA: And I know it's a DAG. Thank you. You're very clever.

---

ETA: On topological sorting (in re EJP's answer): the topological sort algorithms I'm familiar with require you to either:

1. start from "root" nodes n with no incoming edges (i.e., in this scenario, presumably Object and all interfaces without superinterfaces -- which one would have to examine the whole set, plus all superclasses/superinterfaces, to collect) and process all edges (n, m) (i.e., all m extends/implements n, information which again one would have to examine the whole set to collect), or
2. start from "leaf" nodes m with no outgoing edges (i.e., in this scenario, all classes/interfaces m for which no class k extends/implements m exists, which again one would have to examine the whole set to collect) and process all edges (n, m) (i.e., all class/interfaces m extends/implements -- which information we do have).

It's possible one or the other of these multi-pass algorithms (okay, presumably #2) is the most efficient way to do this, but it's certainly not trivially obvious. It's also entirely possible there's a one-pass topological sort algorithm I'm not familiar with, or that I've simply got these algorithms wrong, but in that case, again, "it's basically a kind of topological sort" does not immediately lead one to the answer.

Answer 1

Full working solution to best of my knowledge

• BFS of each class hierarchy going "upwards" - result into LinkedHashSet (preserve order + no duplicates)
• Intersect each set with the next to find anything in common, again LinkedHashSet to preserve order
• The remaining "ordered" set is the common ancestors, first in list is "nearest", last is furthest.
• Empty list implies no ancestors (apart from object)

Code

private static Set<Class<?>> getClassesBfs(Class<?> clazz) {
    Set<Class<?>> classes = new LinkedHashSet<Class<?>>();
    Set<Class<?>> nextLevel = new LinkedHashSet<Class<?>>();
    nextLevel.add(clazz);
    do {
        classes.addAll(nextLevel);
        Set<Class<?>> thisLevel = new LinkedHashSet<Class<?>>(nextLevel);
        nextLevel.clear();
        for (Class<?> each : thisLevel) {
            Class<?> superClass = each.getSuperclass();
            if (superClass != null && superClass != Object.class) {
                nextLevel.add(superClass);
            }
            for (Class<?> eachInt : each.getInterfaces()) {
                nextLevel.add(eachInt);
            }
        }
    } while (!nextLevel.isEmpty());
    return classes;
}

private static List<Class<?>> commonSuperClass(Class<?>... classes) {
    // start off with set from first hierarchy
    Set<Class<?>> rollingIntersect = new LinkedHashSet<Class<?>>(
            getClassesBfs(classes[0]));
    // intersect with next
    for (int i = 1; i < classes.length; i++) {
        rollingIntersect.retainAll(getClassesBfs(classes[i]));
    }
    return new LinkedList<Class<?>>(rollingIntersect);
}

Supporting methods and test

private static void test(Class<?>... classes) {
    System.out.println("Common ancestor for "
            + simpleClassList(Arrays.asList(classes)) + ", Result =>  "
            + simpleClassList(commonSuperClass(classes)));
}

private static String simpleClassList(Collection<Class<?>> classes) {
    StringBuilder builder = new StringBuilder();
    for (Class<?> clazz : classes) {
        builder.append(clazz.getSimpleName());
        builder.append(",");
    }
    return builder.toString();
}

public static void main(String[] args) {
    test(A.class, AImpl.class);
    test(A.class, B.class, C.class);
    test(A.class, AB.class);
    test(AImpl.class, ABImpl.class);
    test(ABImpl.class, ABImpl2.class);
    test(AImpl.class, ABImpl.class, ABImpl2.class);
    test(ABImpl.class, ABImpl2.class, BCImpl.class);
    test(AImpl.class, ABImpl.class, ABImpl2.class, BCImpl.class);
    test(AB.class, ABImpl.class);
}

Output

Common ancestor for A,AImpl,, Result =>  A,
Common ancestor for A,B,C,, Result =>  
Common ancestor for A,AB,, Result =>  A,
Common ancestor for AImpl,ABImpl,, Result =>  A,
Common ancestor for ABImpl,ABImpl2,, Result =>  A,B,
Common ancestor for AImpl,ABImpl,ABImpl2,, Result =>  A,
Common ancestor for ABImpl,ABImpl2,BCImpl,, Result =>  B,
Common ancestor for AImpl,ABImpl,ABImpl2,BCImpl,, Result =>  
Common ancestor for AB,ABImpl,, Result =>  AB,A,B,