CODEWITHSUNDEEP
c++shared-ptrdirected-graphedgesstdset
iteong
iteong

Reputation: 735

Deleting edges for a node in a directed weighted graph that uses smart pointers

I'm pretty new to shared pointers and am trying to delete a node from the graph. When I delete a node, the incoming and outgoing edges stored in that node will be deleted. However, I also need to delete the outgoing and incoming edges (which is the incoming and outgoing edges of the deleted node respectively) of the node that was previously connected to the deleted node - which I call the linking node.

The code below shows my Graph class declarations:

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; }
            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();
        };
..... Some code for node and edge iterators

private:
        std::map< N, std::shared_ptr<Node> > nodes_;

};

For the class to delete the node:

template <typename N, typename E>
void Graph<N, E>::deleteNode(const N& node) noexcept {
    auto findNode = nodes_.find(node);
    if (findNode != nodes_.end()) {

        // find the node which has incoming edges into the deleted node and delete its edges
        for (auto edge: findNode->second->incomingEdges_) { // for each edge in node's incomingEdges_

            // get the origin node of incoming edge to deleted node through dest.lock()
            auto originNodeOfIncomingEdge = edge->dest.lock();

            auto nodeVal1 = originNodeOfIncomingEdge->val_;
            std::cout << "Print out value of origin node of incoming edge to deleted node: " << nodeVal1 << std::endl;

            auto findLinkingNode1 = nodes_.find(nodeVal1);
            std::cout << "size of edges_ in linking node before deleting its outgoing edge (which is the incoming edge of deleted node): " << findLinkingNode1->second->edges_.size() << std::endl;

            auto findEdge = findLinkingNode1->second->edges_.find(edge);
            findLinkingNode1->second->edges_.erase(findEdge);

            std::cout << "size of edges_ in linking node after deleting its outgoing edge (which is the incoming edge of deleted node): " << findLinkingNode1->second->edges_.size() << std::endl;
            --findLinkingNode1->second->numEdges_;

        }

... similar code to above for deleting the node that has outgoing edges from deleted node going into it

        findNode->second.reset(); // deletes managed object of the shared_ptr
        nodes_.erase(findNode); // removes the node from the map container

    }
}

So the main thing that is confusing me is this part, where I'm trying to delete the edge from the for-loop to delete the edge in the linked node.

            auto findEdge = findLinkingNode1->second->edges_.find(edge);
            findLinkingNode1->second->edges_.erase(findEdge);

But I keep getting errors related to shared_ptr. First is related to the pointer:

test8c(2863,0x7fff78df2000) malloc: *** error for object 0x7ffda2403350: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6

Previously, my code for this part is findLinkingNode1->second->edges_.erase(edge); without the findEdge. I was able to compile without any errors, but the edge was not deleted.

Can someone guide me as to how can I delete the edge from edges_ successfully? edges_ is declared as std::set<std::shared_ptr<Edge>> edges_; as shown in the Graph class.

Upvotes: 0

Views: 793

Answers (1)

Sam Varshavchik
Sam Varshavchik

Reputation: 118352

The way things are structured, this is not very efficient. Your Nodes destructor will need to:

  1. Iterate over each of the Edge in the Node being destroyed.

  2. For each Edge get() the other Node.

  3. Find the same Edge in that other Node's list, and delete it.

If this is a frequent operation, I would suggest the following refactoring:

  1. Your Edges hold shared_ptrs to your Nodes.

  2. Your Nodes hold weak_ptrs to your Edges.

Therefore, to delete a Node, you iterate over the node's Edges, and delete them. After all Edges get deleted, all shared_ptrs to the Nodes go out of scope, and the node gets destroyed.

If this is impractical, a less drastic redesign would be:

  1. Assign a unique identifier, of some kind, to each Edge. A simple incrementing counter will do, and it might be possible to handle this in Edge's constructor, automatically.

  2. Refer to all of your Edges using their unique identifier, and instead of a std::set of shared_ptrs of Edges, replace it with a std::map of identifiers, to the shared_ptr for that Edge. This will make it trivial to remove each Edge from the other Node, when destroying a particular Node.

Rather than implementing a discrete identifier, with some care it might be possible to use raw pointers to the Edges, with std::less<Edge *> as their strict weak ordering comparator, as an impromptu unique identifier for each edge.

Upvotes: 0

Related Questions