Clone of an undirected graph

Question

Perform a graph clone. Verifying complexity to be O(E). Looking for code review, optimizations and best practices.

class NodeOfGraph<T> {
 private final T item;
 NodeOfGraph(T item) { 
 this.item = item;
 }
 public T getItem() {
 return item;
 }
}
public class GraphWithCloneFunctionality<T> implements Iterable<NodeOfGraph<T>> {
 /*
 * A map from nodes in the graph to list of outgoing edges. 
 */
 private final Map<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>> graph;
 public GraphWithCloneFunctionality() {
 graph = new HashMap<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>>();
 }
 public GraphWithCloneFunctionality(Map<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>> graph) {
 if (graph == null) {
 throw new NullPointerException("The graph should not be null");
 }
 this.graph = graph;
 }
 /**
 * Adds a new node to the graph. If the node already exists then its a
 * no-op.
 * 
 * @param node Adds to a graph. If node is null then this is a no-op.
 * @return true if node is added, false otherwise.
 */
 public boolean addNode(NodeOfGraph<T> node) {
 if (node == null) {
 throw new NullPointerException("The input node cannot be null.");
 }
 graph.put(node, new HashMap<NodeOfGraph<T>, Double>());
 return true;
 }
 /**
 * Given the two nodes it would add an arc from source 
 * to destination node. 
 * 
 * @param node1 the node1 node.
 * @param node2 the node2 node.
 * @param length if length if string 
 * @throws NullPointerException if node1 or nod2 is null.
 * @throws NoSuchElementException if either node1 or node2 does not exists. 
 */ 
 public void addEdge (NodeOfGraph<T> node1, NodeOfGraph<T> node2, double length) { 
 if (node1 == null || node2 == null) {
 throw new NullPointerException("node1 and node2, both should be non-null.");
 }
 if (!graph.containsKey(node1) || !graph.containsKey(node2)) {
 throw new NoSuchElementException("node1 and node2, both should be part of graph");
 }
 graph.get(node1).put(node2, length);
 graph.get(node2).put(node1, length);
 }
 @Override
 public Iterator<NodeOfGraph<T>> iterator() {
 return graph.keySet().iterator();
 } 
 /**
 * Given a node, returns the edges going outward that node,
 * as an immutable map.
 * 
 * @param node The node whose edges should be queried.
 * @return An immutable view of the edges leaving that node.
 * @throws NullPointerException If input node is null.
 * @throws NoSuchElementException If node is not in graph.
 */
 public Map<NodeOfGraph<T>, Double> edgesFrom(NodeOfGraph<T> node) {
 if (node == null) {
 throw new NullPointerException("The node should not be null.");
 }
 final Map<NodeOfGraph<T>, Double> edges = graph.get(node);
 if (edges == null) {
 throw new NoSuchElementException("Source node does not exist.");
 }
 return Collections.unmodifiableMap(edges);
 }
 /**
 * Clones the graph. Performs deep copy.
 */
 public GraphWithCloneFunctionality<T> clone() {
 final Map<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>> clonedGraph = new HashMap<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>>();
 final Map<NodeOfGraph<T>, NodeOfGraph<T>> cloneMap = new HashMap<NodeOfGraph<T>, NodeOfGraph<T>>();
 for (NodeOfGraph<T> node : graph.keySet()) {
 NodeOfGraph<T> clonedNode = new NodeOfGraph<T>(node.getItem());
 clonedGraph.put(clonedNode, new HashMap<NodeOfGraph<T>, Double>());
 cloneMap.put(node, clonedNode);
 }
 for (Entry<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>> entry : graph.entrySet()) {
 NodeOfGraph<T> source = entry.getKey();
 NodeOfGraph<T> sourceClone = cloneMap.get(source);
 Map<NodeOfGraph<T>, Double> edges = entry.getValue();
 for (Entry<NodeOfGraph<T>, Double> edge : edges.entrySet()) {
 NodeOfGraph<T> destination = edge.getKey();
 NodeOfGraph<T> destinationClone = cloneMap.get(destination);
 clonedGraph.get(sourceClone).put(destinationClone, edge.getValue());
 }
 }
 return new GraphWithCloneFunctionality<T>(clonedGraph);
 }
 public static void main(String[] args) {
 GraphWithCloneFunctionality<Integer> graph = new GraphWithCloneFunctionality<Integer>();
 NodeOfGraph<Integer> nodeA = new NodeOfGraph<Integer>(1);
 NodeOfGraph<Integer> nodeB = new NodeOfGraph<Integer>(2);
 NodeOfGraph<Integer> nodeC = new NodeOfGraph<Integer>(3);
 graph.addNode(nodeA);
 graph.addNode(nodeB);
 graph.addNode(nodeC);
 graph.addEdge(nodeA, nodeB, 10);
 graph.addEdge(nodeB, nodeC, 20);
 GraphWithCloneFunctionality<Integer> graphClone = graph.clone();
 for (NodeOfGraph<Integer> node : graphClone) {
 System.out.print("Node-> " + node.getItem() + " Edges-> ");
 for (Entry<NodeOfGraph<Integer>, Double> node1 : graphClone.edgesFrom(node).entrySet()) {
 System.out.print(" Node : " + node1.getKey().getItem() + " value : " + node1.getValue() + " , ");
 }
 System.out.println();
 }
 }
}

Answer 1

Clone is an ugly API. Josh Bloch has a lot to say about it.

My opinion on it, is that you should use it as a last resort, and, when you do use it, it should be a short-cut to a public copy-constructor.

In other words, your clone method should look like:

public GraphWithCloneFunctionality<T> clone() {
 return new GraphWithCloneFunctionality<T>(this);
}

This way, you have the benefit of the Copy-Constructor, and the functionality of the clone as well, if needed.

After having said all that, I can't see any other significant issues in your code's functionality. It looks about right, and nice and clean.

If you create a copy-constructor, it would look something like:

public GraphWithCloneFunctionality(GraphWithCloneFunctionality<T> tocopy) {
 this(copyGraph(tocopy.graph));
}

The copyGraph function would copy the graph, believe it or not.

Talking about graph-copying, this constructor should take a defensive copy of the graph as well. You don't want to have leaks of graph functionality to outside your class...

public GraphWithCloneFunctionality(Map<NodeOfGraph<T>, Map<NodeOfGraph<T>, Double>> graph) {
 if (graph == null) {
 throw new NullPointerException("The graph should not be null");
 }
 this.graph = graph;
}

The above this.graph = graph is not safe. Use this.graph = copyGraph(graph);

• JavaDeveloper: But I wanted deep-copy.
• rolfl: @JavaDeveloper You can do a deep-copy in the constructor just as easily as you do it in the clone.... also, added more detail to answer (submitted early by mistake).

Answer 2

Your clone() method looks very nice, and I don't have much to say about it except Good Work.

I've read the code a few times, and even then I almost missed this:

/**
 * Adds a new node to the graph. If the node already exists then its a
 * no-op.
 * 
 * @param node Adds to a graph. If node is null then this is a no-op.
 * @return true if node is added, false otherwise.
 */
public boolean addNode(NodeOfGraph<T> node) {
 if (node == null) {
 throw new NullPointerException("The input node cannot be null.");
 }
 graph.put(node, new HashMap<NodeOfGraph<T>, Double>());
 return true;
}

The comment assures the caller that trying to add a node which already exists will be no-op and return false.
In actuality - it will override the existing node, deleting all out-going edges, and return true...

This is another example of how a good unit-test suite is a better documentation than comments.