Удаление ребер для узла в ориентированном взвешенном графе, который использует умные указатели

Я довольно плохо знаком с общими указателями и пытаюсь удалить узел из графика. Когда я удаляю узел, входящие и исходящие ребра, сохраненные в этом узле, будут удалены. Однако мне также необходимо удалить исходящие и входящие ребра (которые являются входящим и исходящим ребрами удаленного узла соответственно) узла, который ранее был подключен к удаленному узлу, который я называю узлом связи.

Код ниже показывает мои объявления класса Graph:

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

};

Чтобы класс удалил узел:

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

}
}

Поэтому главное, что меня смущает, — это часть, где я пытаюсь удалить ребро из цикла for, чтобы удалить ребро в связанном узле.

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

Но я продолжаю получать ошибки, связанные с shared_ptr. Первый связан с указателем:

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

Ранее мой код для этой части findLinkingNode1->second->edges_.erase(edge); без findEdge. Я смог собрать без каких-либо ошибок, но край не был удален.

Кто-нибудь может подсказать мне, как я могу успешно удалить ребро из граней_? dge_ объявляется как std::set<std::shared_ptr<Edge>> edges_; как показано в классе Graph.

0

Решение

То, как все устроено, не очень эффективно. Ваш NodeС деструктором нужно будет:

  1. Итерировать по каждому из Edge в Node быть уничтоженным.

  2. Для каждого Edge get() другой Node,

  3. Найти то же самое Edge в этом другом Nodeи удалите его.

Если это частая операция, я бы предложил следующий рефакторинг:

  1. Ваш Edgeдержать shared_ptrс вашим Nodes.

  2. Ваш Nodeдержать weak_ptrс вашим Edges.

Следовательно, чтобы удалить Nodeвы перебираете узел Edgeи удалите их. В конце концов Edgeвсе удаляется shared_ptrс Nodes выходят из области видимости, и узел уничтожается.

Если это нецелесообразно, менее радикальный редизайн будет:

  1. Назначьте уникальный идентификатор, какой-то, каждому Edge, Подойдет простой инкрементный счетчик, и это может быть возможно в Edgeконструктор, автоматически.

  2. Обратитесь ко всем вашим Edgeс использованием их уникального идентификатора, а вместо std::set из shared_ptrс Edges, заменить его на std::map идентификаторов, к shared_ptr для этого Edge, Это сделает тривиальным удаление каждого Edge от другого Nodeпри уничтожении определенного Node,

Вместо того, чтобы реализовывать дискретный идентификатор, с некоторой осторожностью можно использовать необработанные указатели на Edgeс, с std::less<Edge *> как их строгий компаратор слабого порядка, как импровизированный уникальный идентификатор для каждого ребра.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]