Tracking visited nodes in a graph visitor

Question

I have a graph which I traverse using a typical visitor pattern. I've run into an issue where I need to know if the node being visited has already been visited during the current traversal.

I've developed a solution that I think would work, but it would require creating and destroying node "flags" during/after the graph traversal.

That is, as each node is visited, a flag object pointer member in the node would be checked. If it's NULL, the visitor would create a flag object and assign it to the node's flag object pointer. Then, the visitor would push a reference to the flag pointer member into it's own internal list ( of pointers to flag object pointers, of course ). Otherwise, if the node's flag object pointer isn't NULL, the visitor stops traversal on that node.

Cleanup would then be a matter of popping / deleting the flag objects from the visitor's list after the traversal is complete, and reassigning each node flag pointer in the list to NULL.

It's a bit involved and strikes me as being potentially leak-prone, but I've no better ideas...

Thoughts?

As an addendum, the purpose is to list out in a text console the structure of a tree. If I have several nodes, however, which are parents of a common subgraph, I want to list that subgraph only once and then refer to it using some nomenclature like "[ Subnode1...]" everywhere else.

I mean this for two purposes -

1. I don't want to constantly dump the same data to the screen several times
2. I want a way to visually indicate where a node is simply referencing another part of the existing graph.

As such, setting / clearing a bool as each node is traversed defeats the purpose. I don't want to clear any bools until the root node traversal is complete (i.e., the very last step of the traversal). And, of course, by that point, the question becomes, how do I get all of those flags to reset themselves without re-visiting the entire graph?

Anyway, I'd rather not traverse the graph twice (once to do the work and again to clear flags) or constantly iterate a list each time I visit a node to determine if I've visited it before. The graph isn't large, but it's part of a render subsystem and the traversal occurs between frames, so I want it to make sure it runs quickly...

Answer 1

A simple bool flag in the graph node should do. Set it when visiting a node for the first time or skip the node if already set. After the whole traversal has finished, reset all flags in a separate traversal.

Alternatively, if for some reason you can't change the graph nodes (e.g. because concurrent threads might be traversing it), keep a separate set or unordered_set of pointers to visited nodes. When you reach a node, simply check if it is already in the set, and put it there if it isn't (or skip it if it is).

Answer 2

Typical Visitor pattern for a single Node class:

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

The above defined the generic implementation of a visitor for a graph.
The thing about graphs is that they usually only have one node type so that makes the visitor interface very easy. Now a simple implementation of the visitor interface that makes sure we don't processes nodes more than once.

 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 3

This may very well be a stupid idea, I have not worked much with graphs, but perhaps a bit array?

You find out how many nodes are in the graph you allocate enough bits for that, then during a traversal, when a node is visited the appropriate bit is set and in this manner you know.

Unfortunately I can think of a couple of problems with it off the top of my head. -First, depending on how you perform the traversal, you might find it difficult to know when it is appropriate to mark a node as 'unvisited' depending on you back tracking scheme. -Second, it does not let you track how many times a node has been visited. -Third if the graph is very very large the memory of the array could become quite large, although unless you somehow get your node structure down to a bit per node it would be small compared to the graph. -Fourth, it does not preserve the order in which nodes were visited, though this somewhat ties into the first article.

In the end, unless you have some rare case in which this solution works I would guess that you have probably hit upon one of the better schemes, something like std::vector would do nicely, you can push and pop onto the end, but you can also iterate through the whole thing.