Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

deep copying a graph structure

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.

like image 866
JRR Avatar asked Oct 14 '12 20:10

JRR


People also ask

What is deep copy with example?

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.

What is a clone graph?

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.


2 Answers

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.

like image 144
Tom Anderson Avatar answered Sep 22 '22 02:09

Tom Anderson


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;
    }
like image 26
Sergii Zagriichuk Avatar answered Sep 23 '22 02:09

Sergii Zagriichuk