CODEWITHSUNDEEP
javastructuredeep-copy
Giorgi Margiani
Giorgi Margiani

Reputation: 302

Java Graph (Structure) Deep copy

Well, I have some class (Vertex), that contains HashSet in it; and at some point, I need to deep copy that element;

I wrote some code, but sometimes it doesn't work; I'm working on this bug for several days and can't fix it... If anybody has enough time to read the code and find it, I'll be very grateful. Thank you in advance.

Well, here is function:

public Vertex getCopy(Vertex copyFrom, Vertex copyTo, HashSet<Vertex> created){

    copyTo.setId(copyFrom.getId());
    copyTo.setColor(copyFrom.getColor());
    copyTo.setCount(copyFrom.getCount());
    copyTo.setDepth(copyFrom.getDepth());
    copyTo.setDistance(copyFrom.getDistance());
    copyTo.setHeurist(copyFrom.getHeurist());
    copyTo.setVisited(copyFrom.isVisited());
    copyTo.setPath(copyFrom.getPath());

    created.add(copyTo);

    HashSet<Vertex> copyToNeighs = new HashSet<Vertex>();
    HashSet<Vertex> copyFromNeighs = new HashSet<Vertex>();
    copyFromNeighs.addAll(copyFrom.getNeighbours());

    Iterator<Vertex> it = copyFromNeighs.iterator();

    while (it.hasNext()){
        Vertex curr = it.next();

        if (!created.contains(curr)){
            Vertex newOne = new Vertex();
            newOne = getCopy(curr, newOne, created);
            copyToNeighs.add(newOne);
        } else {
            Iterator<Vertex> itr = created.iterator();
            while (itr.hasNext()){
                Vertex tmp = itr.next();
                if (tmp.equals(curr)){
                    copyToNeighs.add(tmp);
                    break;
                }
            }

        }
    }

    copyTo.setNeighbours(copyToNeighs);

    return copyTo;
}

and i want this method to copy from CopyFrom to CopyTo. here is How i call this method:

Vertex newOne = new Vertex();
Vertex newCurr = new Vertex();
HashSet<Vertex> seen1 = new HashSet<Vertex>();
HashSet<Vertex> seen2 = new HashSet<Vertex>();
newOne = newOne.getCopy(tmp, newOne, seen1);
newCurr = newCurr.getCopy(curr, newCurr, seen2);

other methods (like .getNEighbours(), .addNeighbours())work properly, I've tested them hundreds of time;

Upvotes: 1

Views: 975

Answers (3)

ajb
ajb

Reputation: 31699

created is the wrong concept. You have a set of nodes in the "from" graph, and you're creating a set of new nodes in the "to" graph. created.add(copyTo) will add a new node, from the "to" graph, to the set. But when you go through created.iterator to see if a node is already there, you're looking for a node from copyFromNeighs, which is a node in the "from" graph. It looks to me like this will never succeed. Or else the result will be that you'll have nodes in the "to" graph pointing to nodes in the "from" graph.

Basically, I believe you need created to be a HashMap<Vertex,Vertex>, not a set. The "key" of the HashMap would be a node in the "from" graph, and the "value" would be the corresponding node in the "to" graph. Then, when you look at the neighbors of a "from" node, you get the corresponding "to" node (if it's already been copied) from the map, and add that to the neighbors of your newly created "to" node.

Upvotes: 1

Alexei Kaigorodov
Alexei Kaigorodov

Reputation: 13535

you need more consistent way to map source vertices onto resulting vertices. Declare created as hashmap, not hashset. Create new vertex only when created.get(oldVertex)==null.

Upvotes: 0

lbalazscs
lbalazscs

Reputation: 17784

The simplest way to create a deep copy is to serialize into memory and then deserialize, see this question: How do you make a deep copy of an object in Java?

Upvotes: 0

Related Questions