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.
It means first constructing a new collection object and then recursively populating it with copies of the child objects found in the original. In the case of deep copy, a copy of the object is copied into another object. It means that any changes made to a copy of the object do not reflect in the original object.
Clone Graph. Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a value ( int ) and a list ( List[Node] ) of its neighbors.
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.
Yep, deep copy in java ( not only in java) can be made using memory 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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With