Copy constructor for a directed graph with adjacency list

Question

I am writing a deep constructor copy function for a directed graph:

class Graph {
  class Node {
  private:
    std::vector<Node*> childs;
  public:
    Node* clone() {
      Node* n = new Node(*this);
      for(int i = 0; i < node->childs.size(); i++) {
        n->addChild(childs[i]->clone());
      }
      return n;
    }
  };

  Graph(const Graph& h) {
    root = h.root->clone();
  }

private:
  Node* root;
};

The copy constructor works if I have a tree, but it fails for the following case as it creates two separate clones of B. How do I fix the problem? Do I need to move to the adjacency list representation?

A
|\
|/
B

Can you provide a minimal, complete, and verifiable example? Setting aside the lack of addChild, it looks like your clones have twice as many children as they should. — Barry
– Barry, Commented Sep 10, 2015 at 1:13

Jack · Accepted Answer · 2015-09-10 01:19:06Z

First of all if you have a cycle your code will keep running forever since you are never excluding anything and you didn't specify that we are talking about acyclic graphs.

Second thing, doing Node* node = new Node(*this) already copies the std::vector of nodes, so re-adding them with addChild makes no sense.

This problem could be solved in multiple ways, the first one that comes into my mind is to use a support data structure to avoid cloning same nodes, something similar to:

Graph(const Graph&h) {
  std::unordered_map<Node*,Node*> alreadyCloned;
  root = h.root->clone();
}

Node* clone(std::unordered_map<Node*,Node*>& alreadyCloned)
{
  auto it = alreadyCloned.find(this);

  // if we try to clone a node already cloned just return
  // the clone already created
  if (it != alreadyCloned.end())
    return it->second;

  Node* n = new Node();
  alreadyCloned.insert(this, n); // mark node as clone, so if by recursively visiting we find it, we skip it since we're still cloning

  for(int i = 0; i < this->childs.size(); i++)
    n->childs.push_back(childs[i]->clone(alreadyCloned));

  return n;
}

This code is untested and may have problems, is just to give you the idea behind the approach.

Collectives™ on Stack Overflow

Copy constructor for a directed graph with adjacency list

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related