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

Kinda late input. But I had a similar problem but came to a different solution. But not shure if its bulletproof. So please feel free to comment so I can learn!

I have a Type called "Numbers" because I have no creativity naming stuff. Each object of type "Numbers" has an internal list that can carry additional objects of type "Numbers" of which each has a list of additional "Numbers" of which each... and so on.

Basicaly you can make a tree structure similar to this:

I solved the deep copy problem by using a recursive copy-constructor inside the "Numbers" class.

Numbers class:

import java.util.ArrayList;

public class Numbers {

    private ArrayList<Numbers> numbers = new ArrayList<>();
    private int number;

    public Numbers(int number) {
        this.number = number;
    }

    public Numbers(Numbers numToCopy) {
        this.number = numToCopy.getNumber();
        ArrayList<Numbers> list = numToCopy.getNumbers();
        for(int i = 0; i < list.size(); i++) {
            Numbers n = new Numbers(list.get(i));
            numbers.add(n);
        }
    }

    public void addNumber(Numbers i) {
        numbers.add(i);
    }

    public ArrayList<Numbers> getNumbers() {
        return numbers;
    }

    public void setNumber(int i) {
        this.number = i;
    }

    public int getNumber() {
        return number;
    }

    public ArrayList<Numbers> getAllNumbers(ArrayList<Numbers> list) {
        int size = numbers.size();
        list.addAll(numbers);
        for(int i = 0; i < size; i++) {
            numbers.get(i).getAllNumbers(list);
        }
        return list;
    }

}

Usage:

import java.util.ArrayList;

public class NumbersTest {

    public NumbersTest() {

    }

    public static void main(String[] args) {
        Numbers num0 = new Numbers(0);
        Numbers num1 = new Numbers(1);
        Numbers num2 = new Numbers(2);
        Numbers num3 = new Numbers(3);
        Numbers num4 = new Numbers(4);
        Numbers num5 = new Numbers(5);
        Numbers num6 = new Numbers(6);

        num0.addNumber(num1);
        num0.addNumber(num2);

        num1.addNumber(num3);
        num1.addNumber(num4);

        num2.addNumber(num5);
        num2.addNumber(num6);

        num4.addNumber(num6);

        //Deep copy here!
        Numbers numCopy = new Numbers(num0);
        //Change deep down in graph of original
        num0.getNumbers().get(0).getNumbers().get(1).getNumbers().get(0).setNumber(799);
        //Printout of copy to show it was NOT affected by change in original.
        for(Numbers n : numCopy.getAllNumbers(new ArrayList<Numbers>())) {
            System.out.println(n.getNumber());
        }

    }

}

Usage code shows that changing deep inside the "graph" of the original num0 object, does not change the copy made of it.

Theres two sixes (6) in the graph, and thats ok since they are on different branches. Downside is if same number would repeat through one of the paths, like if there was a (1) somewhere under the first 1. It would then end up in an infinite loop.

Please do comment! :)

Answer 2

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.

Answer 3

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;
    }