iteong iteong - 2 months ago 25
C++ Question

Deep-copy constructor for a new graph

I'm trying to access the edges_ inside my Node Struct, so I can do a for-loop to copy the edges over to a new graph object for my copy constructor.

I'm getting the following error which confuses me when I try to access the edges_ in node.

tests/Graph.tem:280:24: error: ‘struct std::pair<const std::__cxx11::basic_string<char>, std::shared_ptr<gdwg::Graph<std::__cxx11::basic_string<char>, int>::Node> >’ has no member named ‘edges_’
for (auto edge: node.edges_) {
~~~~~^~~~~~


I'm trying to do a copy constructor that deep copies the nodes and edges within a graph over to a new graph object:

template <typename N, typename E>
Graph<N, E>::Graph(const Graph &g):
nodes_{g.nodes_}
{

for (auto node: g.nodes_) {

for (auto edge: node.edges_) {

}

}


}


The following is my Graph class:

template <typename N, typename E> class Graph {

private:
struct Node;
struct Edge;

struct Node {
N val_;
int numEdges_;
int numIncomingEdges_;
std::set<std::shared_ptr<Edge>> edges_;
std::set<std::shared_ptr<Edge>> incomingEdges_;
Node() {}
Node(const N x) : val_{x} { numEdges_=0; numIncomingEdges_=0; }
void printNode(N n);
~Node();
void update();
};

struct Edge {
std::weak_ptr<Node> orig;
std::weak_ptr<Node> dest;
E val_;
Edge(std::shared_ptr<Node> o, std::shared_ptr<Node> d, E x);
Edge() {};
void printEdge();
~Edge();
};


Firstly, how do I access it to do the deep copy? Seems to have some ptr problem. Secondly, is there an easy way to deep copy the edges stored inside the node over?

Answer

For the compiler message, you should replace for (auto edge: node.edges_) by for (auto edge: node.second->edges_)

To perform the deep copy, you need an associative map between the source nodes of g and the nodes of your copy.

Here is an idea of the code I would write for your deep-copy constructor (I have not tried to compile it).

template <typename N, typename E>
Graph<N, E>::Graph(const Graph &g):
    nodes_{g.nodes_}
    {   std::map<Node*, Node*> associativeMap;
        typename std::map<N, std::shared_ptr<Node>>::const_iterator
            thisIter(nodes_.begin()), sourceIter(g.nodes_.begin()),
            thisIterEnd(nodes_.end()), sourceIterEnd(g.nodes_.end());
        for (; thisIter != thisIterEnd; ++thisIter) {
            associativeMap.insert(std::make_pair(&*(sourceIter->second), &*(thisIter->second));
            ++sourceIter;
        }

        thisIter = nodes_.begin();
        for (auto sourceNode: g.nodes_) {
            Node* thisNode = &*thisIter->second;
            for (auto sourceEdge: sourceNode.second->edges_)
               addEdge(*thisNode, *associativeMap[&*sourceEdge->dest], ...);
            ++thisIter;
        }
    }

It is based on a addEge method with the signature void addEdge(Node& origin, Node& destination, ...).

If your Graph::nodes_ are soon sorted and if the addEdge can retrieve the nodes from a key - if its signature is bool addEdge(const N& orig, const N& dest, const E& val) -, the associativeMap is no more useful. In such a case, the code is much simpler.

template <typename N, typename E>
Graph<N, E>::Graph(const Graph &g): nodes_{g.nodes_}
{  for (auto sourceNode: g.nodes_) {
      for (auto sourceEdge: sourceNode.second->edges_)
         addEdge(sourceNode.second->val_, sourceEdge->dest.lock()->val_, sourceEdge->val_);
   }
}