Java, Performing a deep, deep copy of a ArrayList of Nodes that make up a directed graph

Question

I am having issues performing a copy of a Java ArrayList containing Node objects. These Nodes have a HashSet<Edge> of Edge objects that point to other Nodes in the ArrayList to form a directed graph. I need to make a copy of this ArrayList while maintaining the directed graph struture so that I can traverse the copied list just the same as I can with the original list.

The problem is that my deep copy of the list is not "deep" enough. When I copy the array in the method (below) the copies of the Node objects still point to the Nodes in the original array and not in the new array.

How could I change the cloneList function so that it performs a deep, deep copy of the array so that it maintains the directed graph structure in the output array?

public static ArrayList<Node> cloneList(ArrayList<Node> inList)
{
    ArrayList<Node> clonedList = new ArrayList<Node>(inList.size());
    for(Node aNode : inList)
    {
        clonedList.add(new Node(aNode));
    }
    return clonedList;
}

Node

import java.util.ArrayList;
import java.util.HashSet;

public class Node
{
    public String name;
    public HashSet<Edge> inEdges;
    public HashSet<Edge> outEdges;
    public ArrayList<String> deps;

    public Node(String name, ArrayList<String> deps) {
        this.name = name;
        inEdges = new HashSet<Edge>();
        outEdges = new HashSet<Edge>();

        this.deps = deps;
    }
    public Node addEdge(Node node){
        Edge e = new Edge(this, node);
        outEdges.add(e);
        node.inEdges.add(e);
        return this;
    }
    @Override
    public String toString() {
        return name;
    }

    //Used to copy a given node
    public Node(Node inNode)
    {
        this.name = inNode.name;
        this.inEdges = (HashSet<Edge>)inNode.inEdges.clone();
        this.outEdges = (HashSet<Edge>)inNode.outEdges.clone();
        this.deps = inNode.deps;
    }
}

Edge

public class Edge
{
    public Node from;
    public Node to;
    public Edge(Node from, Node to) {
        this.from = from;
        this.to = to;
    }
    @Override
    public boolean equals(Object obj) {
        Edge e = (Edge)obj;
        return e.from == from && e.to == to;
    }
}

score 1 · Accepted Answer · edited May 23 '17 at 10:26

1

Override the clone function in Node and edge to use deep clones (obj.clone()) of the contained objects. For example, for Edge, you can use

 public Edge clone(){
      return new Edge(from.clone(), to.clone());
 }

(provided that you give a clone function for Node).

Then the only issue is collections (Strings are immutable, do not need to be cloned). Use something along the lines of the solution provided in How to clone ArrayList and also clone its contents?

edited May 23 '17 at 10:26

Community

1
1

answered Mar 30 '14 at 19:03

k_g

4,333
2
25
40

So after those overrides, instead of `new Node(aNode)` do `aNode.clone()` in the cloneList method? – KDecker Mar 30 '14 at 19:15
Yes. That should do it. – k_g Mar 30 '14 at 19:18
It is not behaving how I/we would expect. I am not sure of the exact problem. There are other work arounds in the code I have. Thank you for the answer though, it did help me in other areas. – KDecker Mar 30 '14 at 19:30

Java, Performing a deep, deep copy of a ArrayList of Nodes that make up a directed graph

1 Answers1