c++ - 跟踪图形访问者中访问过的节点

Question

我有一个使用典型访问者模式遍历的图表。我遇到了一个问题，我需要知道正在访问的节点是否在当前遍历期间已经被访问过。

我开发了一个我认为可行的解决方案，但它需要在图遍历期间/之后创建和销毁节点“标志”。

也就是说，当访问每个节点时，将检查该节点中的标志对象指针成员。如果为 NULL，访问者将创建一个标志对象并将其分配给节点的标志对象指针。然后，访问者将对标志指针成员的引用推送到它自己的内部列表中(当然，是指向标志对象指针的指针)。否则，如果该节点的标志对象指针不为 NULL，则访问者将停止对该节点的遍历。

清理就是在遍历完成后从访问者列表中弹出/删除标志对象，并将列表中的每个节点标志指针重新分配为 NULL。

这有点复杂，让我觉得可能容易泄漏，但我没有更好的想法......

想法？

作为附录，目的是在文本控制台中列出树的结构。然而，如果我有几个节点，它们是一个公共(public)子图的父节点，我只想将该子图列出一次，然后在其他地方使用诸如“[ Subnode1...]”之类的术语来引用它。

我的意思是有两个目的 -

1. 我不想不断地将相同的数据多次转储到屏幕
2. 我想要一种方法来直观地指示节点在哪里简单地引用现有图表的另一部分。

因此，在遍历每个节点时设置/清除 bool 值就达不到目的。在根节点遍历完成(即遍历的最后一步)之前，我不想清除任何 bool 值。当然，到那时，问题就变成了，如何让所有这些标志自行重置而不重新访问整个图表？

无论如何，我不想两次遍历该图(一次是为了完成工作，另一次是为了清除标志)，或者每次访问一个节点时不断迭代一个列表以确定我之前是否访问过它。该图并不大，但它是渲染子系统的一部分，并且遍历发生在帧之间，因此我希望它确保它快速运行...

Answer 1

单个 Node 类的典型访问者模式:

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);
               }
           }
       }
 };

上面定义了图访问者的通用实现。
图表的特点是它们通常只有一种节点类型，因此访问者界面非常简单。现在是访问者接口(interface)的简单实现，确保我们不会多次处理节点。

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