# Clone of an undirected graph

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.
*/
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);

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();
}
}
}


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);

• But I wanted deep-copy. – JavaDeveloper Apr 7 '14 at 0:45
• @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). – rolfl Apr 7 '14 at 0:48

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.
*/