deep copying a graph structure

Question

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

public class Node {
  List<Node> connections;
}

I would like to make a deep copy of the entire graph. As a first attempt, I tried making a copy constructor like:

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

So deep copying a graph would just be:

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

But that doesn't work as that destroys the connection relationship among the nodes. I am wondering if anyone has suggestions to do this in a simple way? Thanks.

Answer 1

The problem is that you need to copy the identities of the nodes, not just their values. Specifically, when you're copying some node, you need to deal with the identities of the nodes it refers to; that means that a copy constructor, or some other kind of purely local copying mechanism, can't do the job, because it only deals with one node at a time. I'm not sure that makes any sense, but I've typed it and my backspace key doesn't work.

Anyway, what you can do is pass around some other object which can tell which new node corresponds to which old node. If you wanted to be fancy (and who doesn't?) you could refer to this as a graph isomorphism. This 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;
}

Sergii mentions using serialization; serialization actually does something pretty similar when it traverses an object graph.