I'm trying to delete a node for a general directed weighted graph. When I delete a node, I also need to delete the incoming and outgoing edges of that node, so I cannot just delete the node, but also have to delete the edges that are attached to other nodes that used to link to this node before it is deleted.
For the function, I'm trying to find the linking node by using the find() function, which is used to find a node within nodes_, which is declared as:
std::map< N, std::shared_ptr<Node> > nodes_;
I tried originNodeOfIncomingEdge->edges_.erase(edge); but it doesn't work, so I'm trying to do the following in order to find the node on the map of nodes_ before doing an erase.
auto findLinkingNode1 = nodes_.find(originNodeOfIncomingEdge);
However, I keep getting the following error, not sure what is wrong.
tests/Graph.tem:558:64: error: no matching function for call to ‘std::map<std::__cxx11::basic_string<char>, std::shared_ptr<gdwg::Graph<std::__cxx11::basic_string<char>, int>::Node>, std::less<std::__cxx11::basic_string<char> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, std::shared_ptr<gdwg::Graph<std::__cxx11::basic_string<char>, int>::Node> > > >::find(std::shared_ptr<gdwg::Graph<std::__cxx11::basic_string<char>, int>::Node>&)’
auto findLinkingNode1 = nodes_.find(originNodeOfIncomingEdge);
^
In file included from /usr/local/include/c++/6.1.0/map:61:0,
from tests/Graph.h:19,
from tests/test8c.cpp:3:
/usr/local/include/c++/6.1.0/bits/stl_map.h:1079:7: note: candidate: std::map<_Key, _Tp, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::find(const key_type&) [with _Key = std::__cxx11::basic_string<char>; _Tp = std::shared_ptr<gdwg::Graph<std::__cxx11::basic_string<char>, int>::Node>; _Compare = std::less<std::__cxx11::basic_string<char> >; _Alloc = std::allocator<std::pair<const std::__cxx11::basic_string<char>, std::shared_ptr<gdwg::Graph<std::__cxx11::basic_string<char>, int>::Node> > >; std::map<_Key, _Tp, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::pair<const std::__cxx11::basic_string<char>, std::shared_ptr<gdwg::Graph<std::__cxx11::basic_string<char>, int>::Node> > >; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::__cxx11::basic_string<char>]
find(const key_type& __x)
^~~~
This is the code for deleteNode.
template <typename N, typename E>
void Graph<N, E>::deleteNode(const N& node) noexcept {
auto findNode = nodes_.find(node);
if (findNode != nodes_.end()) {
for (auto edge: findNode->second->incomingEdges_) {
// find the node which has incoming edges into the deleted node
auto originNodeOfIncomingEdge = edge->dest.lock(); // origin node of incoming edge to deleted node
auto nodeVal = originNodeOfIncomingEdge->val_;
std::cout << "Print out value of origin node of incoming edge to deleted node: " << nodeVal << std::endl;
// delete the edge from the node
//originNodeOfIncomingEdge->edges_.erase(edge);
auto findLinkingNode1 = nodes_.find(originNodeOfIncomingEdge);
if (findLinkingNode1 == nodes_.end()) throw std::runtime_error("deleteNode: findLinkingNode1 DNE");
}
findNode->second.reset(); // deletes managed object of the shared_ptr
nodes_.erase(findNode); // removes the node from the map container
}
}
The following is some of the declarations of 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; }
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();
};
The error said that originNodeOfIncomingEdge has type std::shared_ptr<gdwg::Graph<std::__cxx11::basic_string<char>, int>::Node> instead of std::string
I believe this is what you want:
auto findLinkingNode1 = nodes_.find(nodeVal);
if (findLinkingNode1 == nodes_.end())
// logic to handle