Отслеживание посещенных узлов в графике посетителя

Question

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

Я разработал решение, которое, как я думаю, будет работать, но для создания и уничтожения узлов «флаги» в ходе/после обхода графика потребуется создать «флаги».

То есть, по мере посещения каждого узла будет проверен элемент указателя объекта флага в узле. Если он равен NULL, посетитель создаст объект флага и назначит его указателю объекта флага узла. Затем посетитель будет ссылаться на элемент указателя флага в его собственный внутренний список (указатели для указателей указателей объектов, конечно). В противном случае, если указатель объекта флага узла не равен NULL, посетитель останавливает обход этого узла.

Очистка будет заключаться в том, чтобы удалить или удалить объекты флага из списка посетителя после завершения обхода и переназначить указатель на указатель узла в списке до NULL.

Это усложнится и ударяет меня как потенциально подверженные утечкам, но у меня не лучшие идеи ...

Мысли?

В качестве дополнения следует указать в текстовой консоли структуру дерева. Однако, если у меня есть несколько узлов, которые являются родителями общего подграфа, я хочу перечислить этот подграф только один раз, а затем обратиться к нему, используя некоторую номенклатуру типа «[Subnode1 ...]» везде.

Я имею в виду это для двух целей -

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

Таким образом, установка/очистка bool по мере прохождения каждого узла поражает цель. Я не хочу очищать любые bools до завершения обхода корневого узла (т. Е. Самого последнего шага обхода). И, конечно же, к этому моменту возникает вопрос, как я могу восстановить все эти флаги, не пересматривая весь граф?

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

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

выше определил общую реализацию посетителя для графа.
Дело в том, что у них обычно есть только один тип узла, что упрощает интерфейс посетителя. Теперь простая реализация интерфейса посетителя, которая гарантирует, что мы не обрабатываем узлы более одного раза.

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

Это может быть очень глупая идея, у меня нет много работал с графиками, но, возможно, с битным массивом?

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

К сожалению, я могу придумать пару проблем с ним с головы. . Во-первых, в зависимости от того, как вы выполняете обход, вам может быть трудно узнать, когда целесообразно пометить узел как «нерассмотренный» в зависимости от вашей схемы отслеживания обратной связи. -Всегда он не позволяет вам отслеживать, сколько раз был посещен узел. -Чтобы, если граф очень большой, память массива может стать довольно большой, хотя, если вы каким-то образом не уберете структуру узла до бита на узел, она будет мала по сравнению с графиком. -Fourth, он не сохраняет порядок, в котором были посещены узлы, хотя это несколько связано с первой статьей.

В конце концов, если у вас нет редкого случая, в котором работает это решение, я бы предположил, что вы, вероятно, нажмете на одну из лучших схем, что-то вроде std :: vector сделало бы красиво, вы можете нажать и всплыть на конец, но вы также можете перебирать все это.

Answer 3

Необходимо указать простой флаг bool в графике. Установите его при первом посещении узла или пропустите узел, если он уже установлен. По завершении всего обхода сбросьте все флаги в отдельном обходе.

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