CSC 162 Taxonomy Project

Spring 2010

As a motivating example for trees, the textbook uses the subject of biological taxonomy, as pioneered by Carl Linnaeus. Living organisms are categorized into one of three domains (Archaea, Bacteria, and Eukarya), each of which is divided into successively smaller categories known as the kindgom, phylum, class, order, family, genus, and species. Human beings, for example, belong to Eukarya, Animalia, Chordata, Mammalia, Primates, Hominidae, Homo, and Homo sapiens, in that order. (There are also sub-categories, but we won’t worry about these.)

Suppose we want to store information about a large collection of organisms—say everything indigenous to a particular island—in a computer database. There are many possible ways to organize the information. Probably the two most common are relational and object-oriented databases. For this assignment, you will build a simple version of the object-oriented variety.

In effect, your database will represent the organisms as a tree of height 8, with life at the root, domains at depth 1, kingdoms at depth 2, and so on. Individual species will be leaves, at depth 8.

Each node of the tree should be an object of class Category:

    class Category:
        def __init__(self, name):

The root of the tree should be referred to by a global variable named life. Each node (Category object) should have the following fields:

parent: reference to another Category, or null for the root of the tree (life).
children: list of (references to) Categories at the next level down the tree, or null is self represents a species.
name: character string (e.g., “Primates”).
depth: 0 for life, 1 for domain, 2 for kingdom, ..., 8 for species.

The Category class should also provide a variety of methods, some of which are listed below. Note: this is not a complete list; you will discover you need more.

classification(self): returns a list giving the names of nodes on the path to the root of the tree, starting with domain (don’t include life) and ending with self. So, if homoSapiens is a reference to the node representing our species, homoSapiens.classification() should return ["Eukarya", "Animalia", "Chordata", "Mammalia", "Primates", "Hominidae", "Homo", "Homo sapiens"].
ancestor(self, depth): returns a reference to the node that is an ancestor at the given depth (or null if self.depth is too low). Should return self if depth == self.depth. Should be called only by the utility routines shown below. Should botch an assertion if depth is less than 0 or greater than 8.
descendants(self, depth): returns a list of (references to) descendants at the given depth (or null if self.depth is too high). Should return self if depth == self.depth. Should be called only by the utility routines shown below. Should botch an assertion if depth is less than 0 or greater than 8.
closestCommonAncestor(self, other): returns the deepest node that is an ancestor of both self and other (in the worst case, 0—life).

def domainOf(self):
    return self.ancestor(1)
def kingdomOf(self):
    return self.ancestor(2)
def phylumOf(self):
    return self.ancestor(3)
def classOf(self):
    return self.ancestor(4)
def orderOf(self):
    return self.ancestor(5)
def familyOf(self):
    return self.ancestor(6)
def genusOf(self):
    return self.ancestor(7)
def speciesOf(self):
    return self.ancestor(8)

def domainsBelow(self):
    return self.descendants(1)
def kingdomsBelow(self):
    return self.descendants(2)
def phylaBelow(self):
    return self.descendants(3)
def classesBelow(self):
    return self.descendants(4)
def ordersBelow(self):
    return self.descendants(5)
def familiesBelow(self):
    return self.descendants(6)
def generaBelow(self):
    return self.descendants(7)
def speciesBelow(self):
    return self.descendants(8)

Finally, you should define a function addOrganism(L) that inserts a new organism into the database. Parameter L should be a list of character strings, just like the ones returned by Category.classification(). Correspondingly, addOrganism should return a reference to the newly created node (or to the appropriate existing node, if the organism is already in the tree). The function should raise the built-in exception ValueError if len(L) != 8.

Reminder

Please read the grading standards web page carefully and follow its instructions. In particular, note that you will need to create a README.txt or README.pdf file, and you will need to turn your code in using Blackboard.

Extra Credit Suggestions

For extra credit (counted at the end of the semester; may raise your final grade), you might consider the following possibilities.

Add support for sub-categories. Homo sapiens, for example, belongs to the sub-phylum Vertebrata. Not all organisms have sub-categories at the same levels; they're introduced into the taxonomy only when needed to capture a particularly “bushy” area of natural diversity. This means not all leaves will be at the same depth in the tree.
Create an iterator version of the descendants method. Use it to create iterator versions of the various xxBelow utility methods.
Extend your code to support constant-time tests for inclusion and disjointness of categories. Specifically, implement methods isContainedIn(other) and isDisjointFrom(other) methods on categories. As described in class, these can operate in constant time if you maintain in every node both the preorder number of the node and the maximum preorder number of any of its descendants. (Symmetrically, you could maintain the postorder number of the node and the minimum postorder number of any of its descendants.)

Due Date: Tues., Mar. 30 at 12:00 noon; no extensions.

Last Change: 25 March 2010 / Michael Scott's email address