G5BADS Coursework: Updateable Directed Graph

FAQ

Design and implement a Java DiGraph class which provides the following public methods:

• DiGraph(): constructs an empty directed graph with no nodes and no edges.
  
• void addNode(Object x): adds a node labelled by the object x to the graph.  If the graph contains a node with a label which  equals() x, does nothing.
• boolean removeNode(Object x): removes the node labelled by the object x from the graph if it is present, otherwise does nothing.  Returns true if the graph contained the specified node.
• boolean containsNode(Object x): returns true if the graph contains a node labelled by the object x and false otherwise;
• void addEdge(Object x, Object y): adds an edge from the node labelled by the object x to the node labelled by the object y to the graph.  If the graph already contains an edge from a node with a label which equals() x to a node with a label which equals() y, does nothing.   If the nodes don't exist, they are created.
• boolean removeEdge(Object x, Object y): removes the edge from the node labelled by the object x to the node labelled by the object y if it is present, otherwise does nothing.  Returns true if the graph contained the specified edge, false otherwise.
• boolean containsEdge(Object x, Object y): returns true if the graph contains an edge from the node labelled by the object x to the node labelled by the object y and false otherwise.
• boolean loops(): returns true if the graph contains a path (sequence of edges) from some node to itself and false otherwise.

  For the graph below, the method will return false. If we added an edge from Boston to London, for example, it would return true because this creates a path (London, New York), (New York, Boston), (Boston, London) from London to itself.

• void print(): which prints the graph as an adjacency list, for example the graph

   
  Moscow <---- London -----> Paris
                 |             ^
                 |             |
                 |             |
                 v             |
               New York ----> Boston
  

  should be printed as follows (the order of nodes not essential):

  Moscow --> 
  London --> Moscow, Paris, New York
  Paris  -->
  New York --> Boston
  Boston --> Paris
  

You may assume that the Objects used as node labels implement the Comparable interface and that the natural ordering is consistent with equals() if you need this for your implementation (for example, if you want to maintain an ordered list of nodes).

Any complete, correct and well-explained solution will get a mark of at least 60. To get a higher mark, you need to provide an efficient implementation of the loops() method.

To test your program for correctness, you can use the following simple menu-driven test called SimpleTest.java (this will also tell you if your method signatures are not what my testing program assumes). Suggestions for efficiency testing will be published next week. Basically, very large graphs (hundreds of thousands of nodes) will be generated using integer arrays (to make node labels out of integers, Integer objects will be created). The graph will be modified using addEdge(Object x, Object y) and removeEdge(Object x, Object y) methods and loops() method is going to be called after each modification.

The submission consists of two parts:

1. the code implementing the DiGraph class; and
2. an essay explaining your solution and containing the big Oh complexity analysis of your implementation of the loops() method (in pdf format: submissions in other formats will not be marked).

Submissions are due at 5pm on Thursday the 27th of November and will be collected electronically from the subdirectory coursework/g5bads of your Private directory (e.g., if your username is abc02u, then the files will be collected from the directory /stud/ug/abc02u/Private/coursework/g5bads).Please ensure that the capitalisation and spelling of your submission directory is correct, otherwise your submission will not be collected.  You will be notified by email when your submission has been successfully collected.  If you don't receive confirmation by the 28th of November, please contact me. Submissions which are not collected due to incorrect spelling etc. will incur 5% penalty. Submissions which are one working day late will be penalised 5%, two working days late 10% and so on (unless your tutor writes to me supporting a request for extension).

You are reminded of the School's Policy on Plagiarism.