그래프 방문자의 방문한 노드 추적하기

Question

일반적인 방문자 패턴을 사용하여 가로 지르는 그래프가 있습니다. 방문중인 노드가 현재 탐색 중에 이미 방문되었는지 여부를 알아야하는 문제가 발생했습니다.

필자는 생각하는 해결책을 개발했지만 그래프 통과 중에/후에 노드 "플래그"를 만들고 파괴해야합니다.

즉, 각 노드가 방문 될 때 노드의 플래그 객체 포인터 멤버가 검사됩니다. NULL 인 경우 방문자는 플래그 객체를 만들어 노드의 플래그 객체 포인터에 할당합니다. 그런 다음 방문객은 플래그 포인터 멤버에 대한 참조를 자신의 내부 목록 (물론 플래그 객체 포인터에 대한 포인터)으로 푸시합니다. 그렇지 않으면 노드의 플래그 객체 포인터가 NULL이 아닌 경우 방문자는 해당 노드에서의 탐색을 중지합니다.

순회는 순회가 완료된 후 방문자 목록에서 플래그 개체를 터벅 터벅으로 삭제하고 목록의 각 노드 플래그 포인터를 NULL로 다시 할당하는 문제입니다.

그것은 ...

생각을 조금 관여 그리고 누수가 발생하기 쉬운 잠재적 인 인상을 받았는데,하지만 난 더 나은 생각을했습니다?

부록으로, 목적은 텍스트 콘솔에서 트리의 구조를 나열하는 것입니다. 그러나 공통 서브 그래프의 부모 인 노드가 여러 개인 경우 해당 서브 그래프를 한 번만 나열한 다음 "[Subnode1 ...]"과 같은 일부 명명법을 사용하여 참조하십시오.

나는 두 가지 목적이 의미 -

내가 지속적으로 화면에 동일한 데이터를 덤프하지 않으
1. 여러 번 노드가 단순히 서로를 참조하고 어디 시각적 방법을 원하는
가 표시 기존 그래프의 일부.

이와 같이, 각 노드로서 bool을 설정/해제하는 것은 목적을 무효로합니다. 루트 노드 탐색이 완료 될 때까지 (즉, 탐색의 마지막 단계) bool을 지우고 싶지 않습니다. 그리고 물론, 그 시점까지, 전체 그래프를 다시 방문하지 않고도 플래그를 모두 다시 설정하려면 어떻게해야합니까?

어쨌든 그래프를 두 번 트래버스하지 않고 (작업을 수행하고 플래그를 지우려면 다시 한번) 노드를 방문 할 때마다 반복적으로 목록을 반복하여 이전에 방문했는지 확인합니다. 그래프는 크기가 크지 않지만 렌더링 서브 시스템의 일부이며 프레임 사이에서 순회가 발생하므로 빠르게 실행되는지 확인하십시오.

Answer 1

일반 방문자 패턴 :

class Node; 
class NodeVisitorInterface 
{ 
    public: 
     virtual ~NodeVisitor() {} 
     virtual bool visitNode(Node& node) = 0; 
}; 

// Note: I have made the accept() method virtual 
//  But if you do derive from node you should add each derived type to 
//  the `NodeVisitorInterface` with its own specific version of visitNode. 
//  
//  What makes graphs easy with the visitor pattern is that there is usually only 
//  one type of node. Thus the visitor interface is trivially easy. 
class Node 
{ 
    public: 
     virtual void accept(NodeVisitorInterface& visitor) 
     { 
      // For the generic this node you call the visitor 
      if (visitor.visitNode(*this)) 
      { 

       // For all linked nodes you get them to accept the visitor 
       // So they can call visitNode() for themselves. 
       // 
       foreach(LinkedNode as node)   // Note pseudo code as I don't 
       {          // know how you specify links 
        node.accept(visitor); 
       } 
      } 
     } 
}; 

위 그래프에 대한 방문자의 일반적인 구현을 정의.
그래프의 경우 일반적으로 노드 유형이 하나뿐이므로 방문자 인터페이스가 매우 쉽습니다. 이제 노드를 두 번 이상 처리하지 않도록하는 방문자 인터페이스의 간단한 구현.

class VisitNodesOnce: public NodeVisitorInterface 
{ 
    public: 
     virtual bool visitNode(Node& node) 
     { 
      if (visitedNodes.find(&node) != visitedNodes.end()) 
      { 
       // Node already handled just return. 
       return false; 
      } 
      // The address of a node should be a unique identifier of the node 
      // Thus by keeping the address of all the visited nodes we can track 
      // them and not repeat any work on these nodes. 
      visitedNodes.insert(&node); 

      this->doWorkOnUniqueNode(node); 
      return true; 
     } 
     virtual void doWorkOnUniqueNode(Node& node) = 0; 

    private: 
     set<Node*> visitedNodes; 
}; 

Answer 2

이것은 바보 같은 아이디어 일 수 있습니다. 그래프를 많이 사용했는데, 아마 비트 배열일까요?

당신은 충분히 많은 비트를 할당 한 그래프에 노드가 얼마나 있는지 알게됩니다. 그리고 나서 순회 중에 노드가 방문되었을 때 적절한 비트가 설정되고 당신이 알게됩니다.

불행히도 내 머리 꼭대기에서 몇 가지 문제를 생각할 수 있습니다. - 먼저 트래버스를 수행하는 방법에 따라 역 추적 스키마에 따라 노드를 '방문하지 않음'으로 표시하는 것이 적절한 지 알기 어려울 수 있습니다. - 둘째, 노드를 몇 번 방문했는지 추적 할 수 없습니다. - 그래프가 매우 큰 경우 배열의 메모리가 상당히 커질 수 있습니다. 노드 구조를 그래프마다 비교하여 노드마다 조금씩 줄이지 않는 한. - 네 번째는 노드가 방문한 순서를 유지하지 않지만 첫 번째 기사와 다소 관련이 있습니다.

결국이 솔루션이 작동하는 몇 가지 드문 경우가 아니라면 더 나은 스키마 중 하나에 부딪혔을 것입니다. std :: vector와 같은 것이 좋을 것입니다. 끝,하지만 당신은 또한 모든 것을 반복 할 수 있습니다. 하나의 노드 클래스의

Answer 3

그래프 노드에서 간단한 bool 플래그를 사용해야합니다. 노드를 처음 방문 할 때 설정하거나 이미 설정된 경우 노드를 건너 뜁니다. 전체 탐색이 완료된 후 별도의 탐색에서 모든 플래그를 재설정하십시오.

그래프 노드를 변경할 수없는 경우 (예 : 동시 스레드가이 노드를 통과 할 수 있기 때문에) 방문한 노드에 대한 포인터로 set 또는 unordered_set을 별도로 보관하십시오. 노드에 도달하면 집합에 이미 있는지 확인하고 노드가 없으면 놓으십시오 (있는 경우 노드를 건너 뜁니다).