똑똑한 포인터를 사용하는 가중치가있는 그래프의 노드에 대한 가장자리 삭제

Question

저는 공유 포인터를 처음 사용하고 그래프에서 노드를 삭제하려고합니다. 노드를 삭제하면 해당 노드에 저장된 들어오고 나가는 가장자리가 삭제됩니다. 그러나 이전에 삭제 된 노드에 연결된 노드 (나가는 노드라고 부르는 노드의 나가는 가장자리와 나가는 가장자리)를 삭제해야합니다.

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 

    } 
} 

그래서 저를 혼란 중요한 것은이 부분은 내가 '곳이다 : 노드를 삭제하는 클래스의

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

}; 

:

는 아래의 코드는 내 그래프 클래스 선언을 보여줍니다 m for-loop에서 가장자리를 지우려고 시도하여 링크 된 노드의 가장자리를 삭제합니다.

  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 

이전에는이 ​​부분에 대한 내 코드가 findEdge없이 findLinkingNode1->second->edges_.erase(edge);입니다. 오류없이 컴파일 할 수 있었지만 가장자리가 삭제되지 않았습니다.

edge_에서 어떻게 가장자리를 성공적으로 삭제할 수 있습니까? edges_는 그래프 클래스에 표시된대로 std::set<std::shared_ptr<Edge>> edges_;으로 선언됩니다.

Answer 1

일이 어떻게 구성되어 있느냐에 따라 효율성이 떨어집니다. Node에서 Edge 각각의 이상

1. 반복 처리가 파괴되고 : 귀하의 Node의 소멸자해야합니다.

2. 각 Edgeget() 기타 Node.

3. 다른 Node의 목록에서 같은 Edge을 찾아서 삭제하십시오. 이 빈번한 작업이 경우

, 나는 다음과 같은 리팩토링을 제안 :

1. 당신의 Edge의는 Node의에 shared_ptr의를 개최.

2. 귀하의 Node은 Edge에 weak_ptr을 보관합니다. 따라서

, 당신은 노드의 Edge의 반복하는 Node 삭제하고, 삭제합니다. 모든 Edge이 삭제 된 후에 shared_ptr이 Node에 도달하면 노드가 삭제됩니다.이 비실용적 인 경우

, 덜 과감한 재 설계는 다음과 같습니다

1. 각 Edge에, 어떤 종류의 고유 한 식별자를 할당합니다. 간단한 증분 카운터를 사용하면 Edge의 생성자에서 자동으로 처리 할 수 ​​있습니다.

2. 은 자신의 고유 한 식별자를 사용하여 Edge의 모든 참조, 대신 Edge s의 std::setshared_ptr의의의, 그 Edge의 shared_ptr에, 식별자의 std::map로 교체합니다. 이렇게하면 각 Edge을 다른 Node에서 제거하고 특정 Node을 삭제하는 것이 간단 해집니다.

오히려 약간주의 이산 식별자를 구현하는 것보다 각 모서리 용 즉석 고유 식별자들은 엄격한 약한 순서화 비교기로서 std::less<Edge *> 더불어 Edge의 원시 포인터를 사용하는 것도 가능하다.