Algorithms and Complexity

The problem statement:

The knowledge, as expressed by the statements above, needs to be represented by a directed and labelled graph. This graph is meant to provide an insight into the world of some species, to be represented by vertices, and their properties, to be represented by labelled edges. This structure shall provide a mini knowledge base, which can provide answers to questions about properties of species, e.g., what is a vegetable.

Your tasks and deliverables:

A) Download the zipped Java skeleton source code (.java files) already implementing a weighted directed graph via an adjacency matrix, together with the text (KnowledgeStatements.txt) input data file including the statements above, as well as the stdlib.jar library. You can do so by
• Logging on to Blackboard at http://www.westminster.ac.uk/blackboard;
• Go to the relevant module Blackboard site, folder Assessment;

B) Unzip and create the project to work with (see also programming assignment checklist below)

C) Modify the logic of the application in the Main class, as well as the implementation of the supportive data structures, i.e., Graph and Vertex, in such a way that the following tasks are accomplished:

1. Populate the graph vertices (nodes) with all concepts/classes appearing in the knowledge statements above. For instance, Food, Apple, Stem Cat, Tabbie, Dog, etc.

2. Populate the graph with edges connecting concepts/classes as of the given statements above. You need to consider that these edges will be labelled by the predicate in the given statements. For instance, Fruit has a stem shall be represented by the nodes ‘Fruit' and ‘Stem' being connected by the directed edge (direction from Fruit to Stem), which will be labelled by the predicate "has a".

3. Implement a console/ terminal type of interaction upon which the following operations can be selected after successful compilation and running of the programme:

a) A DISPLAY method or operation, which displays all the inputted knowledge statements as of the input text file knowledgeStatements.txt, each statement in a different row;

b) A SEARCH method or operation, which receives as input an arbitrary concept/class and returns all meaningful inheritance relationships. For instance, SearchGenealogy(Trout) shall return Fish and Food as an answer.

c) A SEARCH method or operation, which receives as input an arbitrary concept/class and returns all associated features. For instance, SearchFeatures(Fish) shall return has gills, has fins, is food, is animal, as an answer.

4. Estimate the performance in terms of order of growth classifications, for both SEARCH operations, and justify your performance analysis by putting forward comments in plain English on top of the Main class and programme file.

5. Submit a zipped archive of the source and executable code (e.g., in Java, .java and .class files, respectively), ready for compilation and execution.