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

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

2 голосов
/ 16 февраля 2012

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

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

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

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

Это немного запутанно и кажется мне потенциально склонным к утечкам, но у меня нет лучших идей ...

Мысли

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

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

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

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

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

Ответы [ 3 ]

1 голос
/ 16 февраля 2012

Типичный шаблон посетителя для одного класса узла: 

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;
 };
1 голос
/ 16 февраля 2012

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

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

0 голосов
/ 16 февраля 2012

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

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

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

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

...