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

Question

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

Приведенный ниже код показывает мои 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 

    } 
} 

Так что главное, что сбивает с толку меня есть эта часть, где я m пытается удалить ребро из цикла 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. Я смог скомпилировать без ошибок, но край не был удален.

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

Answer 1

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

1. перебирать каждый из Edge в Node разрушается.

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

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

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

1. Ваши Edge s держать shared_ptr с до вашего Node с.

2. Ваш Node s hold weak_ptr s на ваш Edge s.

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

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

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

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

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