# Clone an undirected graph

I'm looking for code-review, optimization and best practices. Also verifying complexity to be O(E) time and O(V+E) space complexity.

final class NodeClone<T> {
private final T item;

NodeClone(T item) {
this.item = item;
}

public T getItem() {
return item;
}
}

final class EdgeClone<T> {

private final NodeClone<T> node1;
private final NodeClone<T> node2;

EdgeClone (NodeClone<T> node1, NodeClone<T> node2) {
this.node1 = node1;
this.node2 = node2;
}

public NodeClone<T> getNode1() {
return node1;
}

public NodeClone<T> getNode2() {
return node2;
}
}

public class CloneGraph<T> implements Iterable<NodeClone<T>> {

/*
*  A map from nodes in the graph to list of outgoing edges.
*/
private final Map<NodeClone<T>, List<EdgeClone<T>>> graph;

public CloneGraph() {
graph = new HashMap<NodeClone<T>, List<EdgeClone<T>>>();
}

public CloneGraph(Map<NodeClone<T>, List<EdgeClone<T>>> graph) {
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.");
}
if (graph.containsKey(node)) return false;

graph.put(node, new ArrayList<EdgeClone<T>>());
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 (NodeClone<T> node1, NodeClone<T> node2) {
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");
}
final EdgeClone<T> edgeClone = new EdgeClone<T>(node1, node2);
}

/**
* Removes an edge from the graph.
*
* @param node1                     If the first node.
* @param node2                     If the second node.
* @throws NullPointerException     if either node1 or node2 specified is null
* @throws NoSuchElementException   if graph does not contain either node1 or node2
*/
public void removeEdge (NodeClone<T> node1, NodeClone<T> node2) {
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).remove(node2);
}

/**
* 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 List<EdgeClone<T>> edgesFrom(NodeClone<T> node) {
if (node == null) {
throw new NullPointerException("The node should not be null.");
}
List<EdgeClone<T>> edges = graph.get(node);
if (edges == null) {
throw new NoSuchElementException("node does not exist.");
}
return Collections.unmodifiableList(edges);
}

@Override
public Iterator<NodeClone<T>> iterator() {
return graph.keySet().iterator();
}

public CloneGraph<T> clone() {
final Map<NodeClone<T>, List<EdgeClone<T>>> clonedGraph = new HashMap<NodeClone<T>, List<EdgeClone<T>>>();
for (Entry<NodeClone<T>, List<EdgeClone<T>>> entry  : this.graph.entrySet()) {
final NodeClone<T> node = entry.getKey();
final List<EdgeClone<T>> edgeList = entry.getValue();

clonedGraph.put(new NodeClone<T>(node.getItem()),  new ArrayList<EdgeClone<T>>(edgeList));
}
return new CloneGraph<T>(clonedGraph);
}

public static void main(String[] args) {
CloneGraph<Integer> graph = new CloneGraph<Integer>();
NodeClone<Integer> nodeA = new NodeClone<Integer>(1);
NodeClone<Integer> nodeB = new NodeClone<Integer>(2);
NodeClone<Integer> nodeC = new NodeClone<Integer>(3);

CloneGraph<Integer> clonedGraph = graph.clone();

Iterator<NodeClone<Integer>> itr = clonedGraph.iterator();
while (itr.hasNext()) {
NodeClone<Integer> node = itr.next();
System.out.println("Item : " + node.getItem());
System.out.println("Edges: ");
for (EdgeClone<Integer> edge : clonedGraph.edgesFrom(node)) {
System.out.println(edge.getNode1().getItem() + " : " + edge.getNode2().getItem());
}
System.out.println();
}
}
}

• Can you describe in more detail what you are trying to do? It seems that you should not create any new classes, but just write a method to clone your original graph. But I'm not quite sure what you are trying to accomplish. Commented Apr 6, 2014 at 16:09
• toto2 I have done the same thing you suggested, but name of my class is very confusing. Commented Apr 6, 2014 at 19:15

looking at it I came across what might be an issue. When you are cloning the graph you create new nodes, that is good. However, the edge objects stays the same so they are pointing to the old NodeClone objects. So this way they are actually pointing to the nodes in the "old" graph and not to the node in the new Graph.

Another point that I was thinking about is if you might want to embed the "clone" feature into the nodes and edges itself. I would suggest couple changed to enable that.

First of all I would add a list of outgoing edges to the NodeClone objects. The reason being is that I think it is more natural to enable the NodeClone itself to know the edges, not to keep this information in the map. Following this opinion, I would also add the incoming edges list.

The counter argument is that you kind of duplicate the information but then you don't need any class Graph. When you insert a new edge or node you simply traverse the structure, which you need to do anyway otherwise you dont know what to connect to what, and "append" the node.

That was about changes to the structure of the graph. After you have that than you could do the cloning method in the following manner. I am going to include direction in the graph because even though you said it is unidirectional but then you use a map and state that the edges are outgoing. Making it unidirectional is easy just look at both incoming and outgoing as same edges.

//In the class EdgeClone
public EdgeClone clone(){
Node from = node1.clone(); //This could be used to introduce the direction in the graph
Node to = node2.clone(); //for the direction of the edge
EdgeClone edge = new EdgeClone(from, to);
}


For the NodeClone you could have something like this:

//In the class NodeClone
private NodeClone copyOfMe; //instance variable to use during cloning
public NodeClone clone(){
if ( this.copyOfMe != null ){ //This is recursion traversal break.
return this.copyOfMe; //If throught the process of cloning the graph I get into the same node through different routes I will not clone it again but just return the prepared copy.
}
NodeClone copyOfMeLocal = new NodeClone(item); //Here it might be worth considering if you want need to clone the item as well
this.copyOfMe = copyOfMeLocal;
//both outgoing and incoming, because if you start in a node that has only incoming edges (a leaf node) nothing would get clones if you would not include here both incoming and outgoing edges.
for(EdgeClone edge: myAllEdges){
edge.clone();
}
this.copyOfMe = null; //copying done, setting this to null
return copyOfMeLocal; //returning valid copy
}


The recursion break in NodeClone method should ensure that you dont get multiple copies of the originally same node when you run the cloning.

This has the advantage that you can start cloning in any node. The disadvantage is that you cannot filter what gets cloned and what not, if you would desire to do so. Complexity should be O(E + V) since you traverse all nodes (V) plus all edges (E), just once.

Hope I provided you with a helpful angle of how this problem could be handled. If you find any discrepancies in my code feel or have additional questions free to comment.

• However, the edge objects stays the same so they are pointing to the old NodeClone objects. - good catch Commented Apr 6, 2014 at 19:12