A function to visit nodes of a graph with C++14

The visitor pattern

Visiting a graph is something useful. You could for example, in a scene graph, want to find all nodes that display a mesh and that have less than some amount of triangles. A classical way to do that is to implement the visitor pattern. Wikipedia (out link) explains clearly enough what this is, but in a nutshell it requires to create a Visitor class and to modify each of the possibly visited class to add a virtual accept function.


class Visitor {

public:
  virtual void visit(ObjectA * object) {
    // do something
  }

  virtual void visit(ObjectB * object) {
    // do something
  }

  // ...

};

class ObjectA {

  // all the ObjectA code

public:
  virtual void accept(Visitor const & visitor) {
    visitor.visit(this);
  }

};

// an so on...

It means that each time you add or remove a new node in your class, you have to update your visitor class, without forgetting to put the accept function. To make it more generic generally the Visitor class is full of abstract functions, and you inherit from it and implement the functions corresponding to the node you are actually interested in. It means, each time you want to visit you have to create a class and override the appropriate functions. It works well, but surely we can do better.

Of course, in order to visit all the nodes of a graph a special case is reserved to nodes that hold children (a group node). When meeting such a node, the visitor will iterate each children to call their accept method with itself, thus visiting the whole graph.

A visitor function

The first thing I wanted when thinking about this is that I do not want to update a Visitor class when I am modifying my graph node types. And the second thing is that I do not want such a class at all. Not touching to the node types would be nice as well. It would be simpler to just give the visitor function, right?

Basically, I want to do something like this:

myVisitorFunction<TypeToVisit>(myTopNode, myFunction);

But, well, I am loosing some flexibility there. With the visitor pattern I could visit several types with each their own function at the same time, so probably what I want is more something like this:

myVisitorFunction<Type1, Type2, ...>(myTopNode, myFunction1, myFunction2, ...);

So how would we declare this? The obvious answer would be using variadic templates:

template <typename... Args, typename Node, typename... Functions>
void visit(Node node, Functions... functions);

But this cannot be for a simple reason: how would the compiler know which types are the node’s and which are the function’s? The solution for that is to use an empty type, used only to hold the types of the nodes:

template <typename... Args>
class Types {};

template <typename... Args, typename Node, typename... Functions>
void visit(Types<Args...>, Node node, Functions... functions);

Not only does it solve our problem but personally I also find that it makes quite a nice syntax to use. See:

visit(Types<NodeType>(), node, function);

That way the types of the nodes to visit look like they are also part of the function parameters, and it makes it quite obvious that you want to visit those types. Of course you are free to disagree with me and find another working syntax if you wish so.

Also you may have noticed that I chose to use a template parameter for the node type. I have a good reason to do so, as you will see if you continue to read 🙂

Implementation

Now that we have the prototype it is time to implement the function. The first thing we want to do is to implement the special case, the case of the group node, we want to iterate over all the nodes of the graph:

template <typename... Args, typename Node, typename... Functions>
void visit(Types<Args...> types, Node node, Functions... functions) {

  static_assert(sizeof...(Args) > 0, "You need to set at least one type");
  static_assert(sizeof...(Functions) == 1 || sizeof...(Args) == sizeof...(Functions), "You need to set as much functions as node types, or only one");

  internal::callIfArg(types, node, functions...);
  auto const group = internal::castNode<GroupNode>(node);

  if (group) {
   for (auto const & n: *group)
     visit(types, internal::getNode(n, group), functions...);
  }

 }

That makes a lot of new things. Lets begin by the static assertions. The first one is obvious: if a type to visit is not given, their is nothing we can do. I decided it should be a compile error, but I could also have defined the function to be empty in that case, depending on what is needed.

The second case is maybe less obvious. The second condition is simple, in that I want the same number of type to visit as to functions to visit the types. Nothing I can do if two functions are given for three types. What should I do then? Well I decided to fail 🙂 The first part of the condition puts a special case. If I have only one function, I will call it on all the given types. It is possible thanks to the auto keyword for the parameters of the lambda. I will probably talk about this in a future article, about tuple value iteration.

I put all the function used internally in a namespace called internal. The first call does what we want, it calls the function if the node given as parameter is of one of the wanted types. The second tries to cast the node to a group node. If the cast succeeds, we then iterate over all the children and visit them too.

As you probably guessed the group node implements a begin() and a end() functions, making it possible to use in the range-based for loop. It contains a vector of std::shared_ptr<Node>, which takes me to the reason why the node parameter has a template type.

When you use the visitor function, sometimes you want to work on the nodes, and in that case raw pointers are sufficient. And sometimes you want to work with the pointers, storing them for example, and you then need a smart pointer. In order for the function to work for both, I took the node type as a template and just specialized the parts needed inside of functions as follows:

namespace internal {
  // cast of the nodes
  template <typename fromNode, typename toNode>
  auto castNode(std::shared_ptr<fromNode> const & node) {
    return std::dynamic_pointer_cast<toNode>(node);
  }
  template <typename fromNode, typename toNode>
  auto castNode(fromNode * node) {
    return dynamic_cast<toNode *>(node);
  }

  // use to keep the same as before, either smart pointer or raw pointer
  template <typename NodeType, typename NodeType2>
  auto & getNode(std::shared_ptr<NodeType> const & node, NodeType &) {
    return node;
  }
  template <typename NodeType, typename NodeType2>
  auto getNode(std::shared_ptr<NodeType> const & node, NodeType *) {
    return node.get();
  }
}

That way the appropriate function is called for the appropriate type, the smart pointer is casted to another smart pointer, the raw to a raw pointer and even if we store smart pointers internally we can continue to use the same kind as pointer as given in the beginning. The second parameter of getNode is only used to determine which of the type of pointer we are using. We can now ignore it in the rest of the implementation.

Now for the actual call if the type matches. Lets first deal with the general case, we have several types and several functions:

namespace internal {
  template <typename Node, typename Function>
  void callIfNode(Node node, Function function) {
    // if the cast succeeded, we call the function
    if (node)
      function(node);
  }

  template <typename Node, typename Function, typename... Functions, typename Arg, typename... Args>
  std::enable_if_t<(sizeof...(Functions) > 0)> callIfArg(Types<Arg, Args...>, Node node, Function function, Functions... functions) {
    // we first verify the current type, then we try the next one
    callIfNode(castNode<Arg>(node), function);
    callIfArg(Types<Args...>(), node, functions...);
  }
}

Each time the function is called, we strip one node type and one function from the list and we continue. The enable_if is there to avoid a conflict with the next function by ensuring there are at least two functions left, making it silently disappear with SFINAE if it is not the case. Now in the case we have only one function left, which is also the case if we give several node types and only one function to visit:

namespace internal {
  template <typename Node, typename Function, typename Arg, typename... Args>
  inline void callIfArg(Types<Arg, Args...>, Node node, Function function) {
    // same as before but with only one function
    callIfNode(castNode<Arg>(node), function);
    callIfArg(Types<Args...>(), std::forward<Node>(node), function);
  }
}

It works the same as the previous one, but always keep the same function. And finally, when all the node types are tested, we have nothing left to do:

namespace internal {
  template <typename Node, typename Function>
  inline void callIfArg(Types<>, Node, Function) { /* empty */ }
}

Conclusion

So what is your opinion, dear reader? The main part is that once implemented it is really easy to use and completely agnostic of the type of the node of the graph, except for the group node of course. You use it like this:

visit(Types<NodeType1, NodeType2>(), myTopNode, [] (auto node) {
  // do something
});
Advertisements

5 thoughts on “A function to visit nodes of a graph with C++14

  1. Pingback: A simple signal system | About C++

  2. Pingback: Непросмотренные ссылки – 8 | Откомпилируй Это

  3. Really interesting. I love the Visitor pattern but I always thought that having an interface with an overload of the visit method for all possible sub-types is quite restrictive, so I don’t implement it often.
    Your solution is quite elegant but I wonder if all the calls to dynamic_cast would not hurt significantly the performances of the traversal in the case of a lot of types to potentially test for.

    Like

    • I wondered the same thing actually but I did not measure anything and it was not the point of the article anyway. But I believe that a dynamic cast would not be so different compared to a virtual function call, so I suppose as you say that the more node types the less efficient it becomes compared to a classic implementation.

      Like

  4. Hi I am so glad I found your website, I really found you by accident, while I was researching on Yahoo
    for something else, Anyhow I am here now and would just like to say thanks for a
    tremendous post and a all round interesting blog (I also love
    the theme/design), I don’t have time to go through it all
    at the minute but I have bookmarked it and also added your RSS feeds, so when I have time I will
    be back to read much more, Please do keep up the awesome b.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s