Java Programming

Background: Phylogenetic Trees

A phylogenetic (or evolutionary) tree represents the evolution of species over time. Each node in the tree corresponds to a species and parent-child relationship represents an evolution from one species to another. Scientists build such trees based on genetic and fossil data, indicating that one species evolved from another. In particular, given a sequence of statements of the form "X evolved from Y", a computer can be used to build a phylogenetic tree.

Problem: Generating a Phylogenetic Tree

Given a series of statements of the form "X evolved from Y", where X and Y denote species, construct a corresponding phylogenetic tree. For example, given the input

leeches evolved from flatworms cecil evolved from snakes monkeys evolved from one-celled forms lochness monster evolved from snakes snakes evolved from one-celled forms flatworms evolved from one-celled forms fung evolved from sponges sponges evolved from one-celled forms end

Your task is to create a program that generates phylogenetic tree based on phylogenetic data and output a representation of the tree.

Write a program called EvoTree.java that reads in phylogenetic data from the console (System.int) and outputs the corresponding phylogenetic tree. Your EvoTree class must implement the provided Tester interface and also contain the main() method where your program starts running. This is because your program will be tested via this interface. The interface contains a single method:

public ArrayList compute( Scanner input );

This method must perform the required computation.

Input

The compute() method takes a Scanner object, which contains one or more lines. Each line, except the last one, is of the form

Species A evolved from Species B where Species A and Species B are names of speci c species. The species names can comprise one or more words, but will never contain the words "evolved from". The last line of input is simply the word "end". See Figure 2 for an example.

Hint: Use the nextLine() method of the Scanner object to read one line of input at a time, and then parse the line. See the solution for Assignment 1 for how to parse input one line at a time.

Semantics

Each line of the form "Species A evolved from Species B" represents a direct evolution from species B to species A. The input lines are in arbitrary order. All data will generate a single tree. That is, there will only be one species that is not evolved from some other species (the root of the tree). Each species (except the root) will be evolved from exactly one species, but multiple species may evolve from a single species, as in the example. (This is a simplification.)

Hints and Suggestions

The sample solution uses a 2-pass algorithm. The first pass builds the phylogenetic tree. This can be done iteratively. The second pass recursively outputs the tree.

Figure 2: Sample phylogenetic data. the result phylogenetic tree would look like one-celled forms I-flatworms I I-leeches I -monkeys I-snakes I I-cecil I I-lochness monster l-sponges I I-fung Figure 3: A representation a phylogenetic tree generated from data in Figure 2 Figure 2: Sample phylogenetic data. the result phylogenetic tree would look like one-celled forms I-flatworms I I-leeches I -monkeys I-snakes I I-cecil I I-lochness monster l-sponges I I-fung Figure 3: A representation a phylogenetic tree generated from data in Figure 2