G5BADS Coursework: FAQ

• Efficiency of loops(). Efficient implementation should have the same complexity as depth-first search of a graph (should be finished in one passage through the graph). For timing on large graphs, you can use Test.java . Efficient code ran on marian this afternoon in about 2-3 seconds.
• Can I write several classes (including inner classes)? Yes, all .java files in your coursework submission directory will be collected and compiled.
• How do I call the pdf file? Does not matter, we will collect all files in your coursework submission directory. Make sure there is just one pdf file for me to mark.
• Here is information about Java 1.4 API.
• Before you ask me questions on how to start, type in the code for LinkedGraph from the graph implementation lecture and try to add a couple of methods to it, like containsNode or containsEdge.
• There is a reasonable adjacency list implementation of graphs in the book by Duane Bailey, Java Structures .
• After removeNode(x) is called, also the edges involving x should be removed (if I call containsEdge(x,y) or containsEdge(y,x) after x is removed, the answer should be "false" even if the edge was there before).
• If you wrote a special class for Node and/or Edge and then try to find out whether a Node x is in a list of nodes (say) by calling list.contains(x) the test will be done by calling equals(x) on all the elements of the list. This means that if you do not overwrite the equals() method for nodes, you may get unexpected results. (The default equals() method for Objects returns true only if the two objects have the same reference. You probably want true to be returned if they have the same Object label or, for Edges, the same start and destination).
• Should adding an edge from the node to itself generate an error? No, addEdge("London", "London") should work as normal.
• I have a variable x of type Object and I want to call x.clone(), but I get a compiler error. Why do I get the error and how do I fix this?

  clone() is a protected method in Object. This means that it is accessible by files in the same package (java.lang) and by subclasses, which should be fine since everything is a subclass of Object. However, there is a caveat: see Sun Java Tutorial. Basically, in a user defined class C from a different package (not java.util) you can invoke a protected method of Object on objects of type C and its subclasses, but not on objects of type Object. In particular, you cannot invoke clone() on Objects from a class DiGraph.java.

  There is really no way to fix this: you need to restructure the program so that you don't try to destroy or modify the references to graph label Objects I pass you. About modifying the graph, see below.

• My loop method updates the graph destructively (for example, doing topological sort and removing nodes and edges). How do I make a deep copy of the graph (so that if I change the copy, the original graph does not change)?

  The simplest way is to introduce a way to mark nodes and edges as deleted without changing anything else. This is actually faster than making a proper copy, then really destroying things and waiting for the garbage collector to collect them. Don't forget to unmark things when you are finished.
  For example, if you have a GraphNode class, you can introduce a boolean flag in it saying whether it is deleted. If you have another implementation, you can have a HashMap where you put a mark against a node/edge which is deleted (to see if x is deleted, you ask deletedhash.containsKey(x)).
  If you have, say, a LinkedList or a HashMap called mygraph storing GraphNodes or Objects and you want to make a copy of it called copygraph, the surest way is to iterate through mygraph, and insert each object stored in mygraph into a copygraph. If afterwards you remove something from copygraph, it will still be in mygraph. Note that if you modify one of the entries x in the copygraph (e.g. if x is a GraphNode and you change its label or its neighbours), the same thing happens to x in mygraph.

• One of your tests uses Strings as node labels, and another uses Integers. Which ones should I use in my implementation?

  Your graph should have labels of type Object. This way it will work if I pass it labels of type String and if I pass it labels of type Integer (or any other object).

• You mention that the label Objects will implement Comparable, but from what I can see, the java compiler will only accept the compareTo method if it is sure that the Object implements Comparable, and it cannot be unless it knows the class of the Object.

  You fix this by casting to Comparable. If you are passed an Object x and you want to compare it to another Object y, then to keep the compiler happy you do ((Comparable) x).compareTo(y). If at runtime I pass you x which is not Comparable (unlike String or Integer) there will be a casting exception thrown, but I promised that I will only use Comparables.

• Concerning the essay: do you mean that we are too write an essay on how all of the methods work (addNode, addEdge etc) or just explain how the loops method works. Also do you want the precise time calculating or just the order of the time complexity analysis calculating.

  I'd like to have a general description of your solution so that I understand how your program works, e.g "I have GraphNodes with such-and-such fields and I keep them in a LinkedList and when I need to check for an edge (x,y) I go looking for the node with the source label x first, and then check if that node has a link to the node with the destination label y". I just need a summary so that it is easier to read your code and understand loops().

  For the complexity, I don't want you to write a very detailed counting of all operations, but I want a justification for you big O answer, not just "it is quadratic", but why. See, for example, the working out in the lecture of the BFS complexity.

• Page limit on the essay - the essay should be 2-3 pages, if you have a very complicated program can add one more page.
• I am interested in time complexity of loops() (not space).
• Percentage of essay and program: for normal submissions about 50-50 but in some cases I can't just add it up (like if there is no program).
• How to make a pdf file starting from Word on Windows:
  1. select Print, make sure default printer is postscript printer like het and vav, and choose "print to file" which will produce filename.prn.
  2. Move filename.prn to H: drive, Private folder.
  3. Log in to robin, tuck, or other Solaris machine.
  4. do

     cd Private
     mv filename.prn filename.ps
     distill filename.ps