CODEWITHSUNDEEP
c++shared-ptrcopy-constructordeep-copydirected-graph
iteong
iteong

Reputation: 735

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?

Upvotes: 0

Views: 1053

Answers (1)

Franck
Franck

Reputation: 1635

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

Upvotes: 1

Related Questions