This question was adapted, with permission, from a question originally written by Boris Motik.
Consider the implementation of a graph node given in:
Your task is to extend GraphNode with cloning facilities. Remember that
Object provides a protected method, clone. If invoked on
an object that does not implement the Cloneable interface, this method throws a
CloneNotSupported exception. Otherwise, it creates a new object that is bitwise
identical to the original, and returns a reference to it.
What are the implications of making a bitwise identical copy of an object? In particular, what does this imply for reference fields of the object? In the cloned object, will such fields point to fresh objects that have been recursively cloned?
Your implementation of clone for GraphNode should create a "semi-deep"
copy of a GraphNode. That is, the node object and all its (directly and indirectly)
reachable children should be cloned, but the objects representing node keys should not be cloned.
Your implementation should correctly handle cyclic graphs.
As a warmup, to understand the Cloneable
interface, add a public method foo to graph node. This method should simply call the clone()
method from Object. You should find that this method does not compile, because clone() may
throw a CloneNotSupportedException, which is a caught exception. Add a throws clause
to the method. Now, in a separate class, write a main method that creates a GraphNode and calls foo on the resulting
object. Surround this call in a try-catch block to catch a CloneNotSupported exception, if it is thrown.
When you run main, you should find that such an exception is thrown. This is because GraphNode
does not implement the Cloneable interface.
Make GraphNode implement the Cloneable interface. Notice
that you need do nothing other than write implements Cloneable for this purpose. In particular, Cloneable
does not specify any methods. Perhaps surprisingly, it does not specify the clone() method: this comes from Object.
Implementing Cloneable simply says: "I, the developer of this class, am agreeable to the class being cloned!". Now you should
find that when you run your main method, no exception is thrown.
Delete the method foo. Instead, try to call clone() directly
on a GraphNode from main. You should find that your program does not compile. This is due to clone
having the following signature in Object:
protected Object clone() throws CloneNotSupportedException;
Why is this a problem? Why was it possible to call clone() from within foo()?
The meat of the question.
In GraphNode, override clone(), changing the visibility of the method to public. The return
type of your overriding clone() method should be as specific as possible, and if possible your method should
not throw any exceptions. There are some hints below that may help you in implementing this method. The challenge
here is to make sure your method correctly handles cyclic graphs.
Test that your cloning functionality works: all assertions in the following test program should pass:
public static void main(String[] args) {
// Make some nodes
GraphNode<String> original = new GraphNode<String>();
original.setKey("Hello");
GraphNode<String> child1 = new GraphNode<String>();
child1.setKey("Child 1");
GraphNode<String> child2 = new GraphNode<String>();
child1.setKey("Child 2");
// Join them up
original.addSuccessor(child1);
original.addSuccessor(child2);
child1.addSuccessor(original); // Creates a cycle
child2.addSuccessor(original); // Creates a cycle
// Clone original
GraphNode<String> clone = original.clone();
// Check that the clone uses distinct nodes
assert original != clone;
assert original.getSuccessor(0) != clone.getSuccessor(0);
assert original.getSuccessor(1) != clone.getSuccessor(1);
assert original.getSuccessor(0).getSuccessor(0) != clone.getSuccessor(0).getSuccessor(0);
assert original.getSuccessor(1).getSuccessor(0) != clone.getSuccessor(1).getSuccessor(0);
// Check that original has cycles
assert original.getSuccessor(0).getSuccessor(0) == original;
assert original.getSuccessor(1).getSuccessor(0) == original;
// Check that clone has corresponding cycles
assert clone.getSuccessor(0).getSuccessor(0) == clone;
assert clone.getSuccessor(1).getSuccessor(0) == clone;
// Check that original and clone share same keys
assert original.getKey() == clone.getKey();
assert original.getSuccessor(0).getKey() == clone.getSuccessor(0).getKey();
assert original.getSuccessor(1).getKey() == clone.getSuccessor(1).getKey();
}
It should be possible to give clone() the following signature:
@Override
public GraphNode<E> clone();
Think about why this is much more useful than the signature provided by Object. Also think about why it is OK for this method to
override the Object version, even though it has a different signature. Why does this method not throw a CloneNotSupportedException?
In implementing clone(), it will be useful to have a private helper method, internalClone(). This method should use
super.clone() to create a straightforward clone of the graph node. This takes care of copying the graph node's key. After making
such a clone, internalClone should reset the successors field of the resulting object. When you call super.clone(),
the compiler thinks that a CloneNotSupportedException may be thrown. You know that this will not happen---why? Because you know it cannot
happen, you can surround the call with a try-catch block, and be confident that the catch block will never be reached. To keep the compiler happy,
the catch block has to return something; think about what special value will do. You will also find that super.clone() returns an
Object, which you will need to cast appropriately.
Now to implement Clone, you can keep a map from old nodes to new nodes:
Map<GraphNode<E>, GraphNode<E>> oldToNew = new HashMap<GraphNode<E>, GraphNode<E>>();
First, do a depth-first search of the graph rooted at the current node. This can be achieved by creating a Deque<GraphNode<E>>
object, and using it as a stack. Push this on to the stack. Then while the stack is not empty, pop an element, old say, from the stack.
If oldToNew does not contain the element as a key, use internalClone to make a clone, newNode say. Put the
pair (old, newNode) into the oldToNew map. Now push each successor of old on to the stack.
Once this process has been completed, you have a new node for each graph node. However, the successor fields of the new nodes have not been set up.
To do this, you should iterate through the key set of oldToNew. For each old node that is a key, consider all of its successors.
In each case, if old node n has successor m, you should add oldToNew.get(m) as a successor of oldToNew.get(n).
This sort of cycle-aware programming is difficult. Give the exercise a good go, and if you get stuck take a close look at the model answer.