Deep copying graph structure

Question

I have a graph class with Node's where each Node can connect to the others:

public class Node { List<Node> connections; } 

I would like to make a deep copy of the entire chart. As a first attempt, I tried to create a copy constructor, for example:

 public Node(Node other) { connections = new ArrayList<Node>(); for (Node n : other.connections) { connections.add(new Node(n)); } } 

Thus, deep copying of the chart would be as follows:

 public Graph deepCopy () { Graph g = new Graph(); g.nodes = new ArrayList<Node>(); for (Node n : nodes) { g.nodes.add(new Node(n)); } } 

But this does not work, as it breaks the connection between nodes. I am wondering if anyone has any suggestions to do this in a simple way? Thanks.

Answer 1

The problem is that you need to copy the node IDs, not just their values. In particular, when you copy some nodes, you need to deal with the identifiers of the nodes it refers to; this means that the copy constructor or some other mechanism of purely local copy cannot do this work, since it only deals with one node at a time. I'm not sure if this makes sense, but I typed it and my backspace key is not working.

In any case, what you can do is pass another object that can determine which new node corresponds to the old node. If you want to be a fantasy (and who not?), You can call it a graph isomorphism . It can be something as simple as a map. As in this completely untested code:

 // in Graph public Graph deepCopy () { Graph g = new Graph(); g.nodes = new ArrayList<Node>(); Map<Node, Node> isomorphism = new IdentityHashMap<Node, Node>(); for (Node n : nodes) { g.nodes.add(n.deepCopy(isomorphism)); } return g; } // in Node public Node deepCopy(Map<Node, Node> isomorphism) { Node copy = isomorphism.get(this); if (copy == null) { copy = new Node(); isomorphism.put(this, copy); for (Node connection: connections) { copy.connections.add(connection.deepCopy(isomorphism)); } } return copy; } 

Sergius mentions the use of serialization; serialization actually does something quite similar when it crosses an object graph.

Answer 2

Yes, a deep copy in java (not just in java) can be done using serialization/deserialization like this

 public static Object copy(Object orig) { Object obj = null; try { // Write the object out to a byte array ByteArrayOutputStream bos = new ByteArrayOutputStream(); ObjectOutputStream out = new ObjectOutputStream(bos); out.writeObject(orig); out.flush(); out.close(); // Make an input stream from the byte array and read // a copy of the object back in. ObjectInputStream in = new ObjectInputStream( new ByteArrayInputStream(bos.toByteArray())); obj = in.readObject(); } catch(IOException e) { e.printStackTrace(); } catch(ClassNotFoundException cnfe) { cnfe.printStackTrace(); } return obj; }