1
$\begingroup$

What is an algorithm that will take as an input a flat list of objects with a varying degree of overlapping properties:

thing1 (instance of "Mammal", but we don't know this now)
  -eatsFood
  -reproduces
  -hasMilk

thing2 (instance of "Emu", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -doesNotFly

thing3 (instance of "Eagle", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies

thing4 (another instance of "Eagle", we just know it has the same "shape" as thing 3)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies

thing5 (instance of "BaldEagle", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies
  -hasWhiteHead

And return as an output a hierarchical class structure/inheritance tree/taxonomy like the following?

enter image description here

Notes:

  1. The algorithm is able to identify a hierarchical structure in the objects' properties, including abstract classes that are not explicitly present as objects in our data set. For example, there are no instances of "Bird" or "Animal" in our object data set, however the algorithm is able to identify that "Eagle" and "Emu" both inherit from a common parent class (the abstract class "Bird") and that both the "Bird" and "Mammal" classes inherit from a common parent class (the abstract class "Animal").
  2. The algorithm doesn't know or care about the class names ("Animal", "Mammal", "Bird", "Emu", "Eagle", "Bald Eagle"). We generate those ourselves based on the properties of the classes the algorithm has generated. I just put them here to aid the example, but they're not part of the algorithm.
  3. The list of an object's properties in the data set will not necessarily be "in order" like they are here. Don't assume any order to the properties in the raw data.
$\endgroup$
  • $\begingroup$ Are you guaranteed that this will be a tree (single inheritance only), or might it form a dag (i.e., multiple inheritance)? $\endgroup$ – D.W. Apr 21 '18 at 5:03
  • 1
    $\begingroup$ I don't understand how an algorithm could possibly know to create an extra class for "Bird", given the inputs you have shown. Why wouldn't the algorithm create an alternative hierarchy where there is no "Bird" and where both Emu and Eagle are immediate children of Animal? That is also equally consistent with the input data. I don't see any way to choose between those two candidate hierarchies. Are both acceptable? Can you provide a general specification of the problem? A single example is not a substitute for a clear and general statement of the problem. $\endgroup$ – D.W. Apr 21 '18 at 5:07
  • $\begingroup$ With the data I'm working with it should only be a tree/single inheritance. $\endgroup$ – davidlav Apr 21 '18 at 5:07
  • $\begingroup$ I should have added that the algorithm would identify "abstract classes" like Bird if it sees that that at least two sibling classes share properties that could be abstracted. And I apologize for the presentation of the problem. I'm an engineer/programmer and don't have a great grasp of theory or how to properly state the problem beyond what I've written here. $\endgroup$ – davidlav Apr 21 '18 at 5:21
  • 1
    $\begingroup$ Now another follow-up. Suppose you have three objects, as follows: obj1: eatsfood, hasfeathers; obj2: eatsfood, flies; obj3: hasfeathers, flies. What do you want the output to be? I can see at least three possible hierarchies that appear to comply with all of your requirements (you can form an abstract base class C1 of obj1+obj2, then an abstract base class D1 of C1+obj3; or C2 from obj1+obj3 then D2 from C2+obj2; or C3 from obj2+obj3 then D3 from C3+obj1). When there are multiple hierarchies that are consistent with the data, are you OK if the algorithm produces any of them? $\endgroup$ – D.W. Apr 21 '18 at 5:44
1
$\begingroup$

It looks like your problem can be solved by transitive reduction followed by some post-processing.

Build a directed graph, with one vertex per "object shape". Draw an edge $u \to v$ if $u$ contains all of the fields of $v$ (possibly plus some more). This should form a dag. Now compute the transitive reduction of this dag. The result should be a tree (or forest of trees).

This almost gives you the desired solution. The one thing it doesn't do is invent new abstract base classes that weren't already present in the input. So, we can do some post-processing to create them. First, if the result has more than one tree, we'll create a new root (an abstract base class) that is a parent of all of those trees. The result is a (directed) tree.

Examine each node that has more than two children. This is the only place where we need to create new abstract base classes. Let $S$ denote the set of children. Now you have some choices about how you want to form a hierarchy based for $S$; there are multiple possibilities that are all consistent with the input data, and the question doesn't specify any criteria for choosing among them. So, I'll have you let you decide on how you want to select among them.


What's the running time? Constructing the graph and computing the transitive reduction can be done in $O(n^3)$ time, where $n$ is the number of different object shapes present in the input. (In fact, given the structure of the input, in this particular case it can actually be done in $O(n^2)$ time, but maybe that isn't important, since I suspect in practice $n$ might be fairly small.) The post-processing can also be done in $O(n^3)$ time (probably less if you care). So the overall running time is at most $O(n^3)$.

Of course, we can de-duplicate the shapes in the input before doing any processing: there is no need to keep more than one object of any particular shape. So, the running time depends only on $n$, the number of distinct shapes in the input, not on the number of objects in the input. It's easy to do the de-duplication in linear time using a hash table.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.