How to implement a directed acyclic graph DAG at compile time in C++

Question

I am looking for an advice on how to implement a DAG in C++ using templates. The main idea is to design a kind of framework where users can bring their own classes (Nodes) to perform some work on the input provided by other Nodes. Given this relation between the classes a DAG seems like a natural choice. At the same time I would like to avoid relying on virtual abstract interfaces as I think it is clearer for users to implement a work method with a signature explicitly stating all required inputs, e.g. Node::process(const AnotherNodeA&, const AnotherNodeB&) rather than Node::process(const set<AbstractNode*>&).

I think I figured out how to implement an hierarchy of types by using type lists. For example, the following implements a simple graph like this:

strict digraph "" {
  NodeY -> Node1;
  NodeX -> Node1;
  Node1 -> NodeA;
  NodeX -> Node2;
  Node2 -> NodeB;
  NodeY -> NodeB;
}

#include <iostream>
#include <typeinfo>

template<class... T> struct NodeList {};

template<typename... InpNodes>
struct Node
{
  using Inputs = NodeList<InpNodes...>;
};

struct NodeX : Node<> {};
struct NodeY : Node<> {};

struct Node1 : Node<NodeX, NodeY> {};
struct Node2 : Node<NodeX> {};

struct NodeA : Node<Node1> {};
struct NodeB : Node<Node2, NodeY> {};

template <size_t D>
void print_list() {}

template <size_t D=0, typename N, typename... Rest>
void print_list(const N&, const Rest&... rest)
{
  for (int i=0; i<D; ++i) std::cout << "\t";

  std::cout << typeid(N).name() << "\n";

  print_list<D+1>(typename N::Inputs());
  print_list<D>(rest...);
}

template <size_t D=0, typename... Types>
void print_list(const NodeList<Types...>& lst)
{
  print_list<D>(Types()...);
}

int main()
{
  using NList = NodeList<NodeA, NodeB>;
  print_list(NList());

  return 0;
}

The above prints the hierarchy of the defined types:

NodeA
        Node1
                NodeX
                NodeY
NodeB
        Node2
                NodeX
        NodeY

Would std::pair<ChildNode, ParentNode> be a good choice to implement the "edges" between the nodes, i.e. ChildNode -> ParentNode? Can a set of such defined pairs be used to verify and/or sort the nodes topologically?

Beanfeast

Thanks for the pointer. I looked through the code but I don't see a simple example that could help me to understand it from the user's perspective. – Beanfeast

You could also look inside the source code of existing open source C++ compilers (e.g. Clang or GCC....). They are solving the same problem (since internal representations inside compilers are DAG) – Tiedeman

Are you allowed to code a simple C++ code generator? If you are, it is simple. You could use parser generator tools like ANTLR or GNU bison or preprocessors like GNU m4 or GPP. If you are fobidden to generate C++ code, things are much more complex – Tiedeman

In what interface would your nodes be communicating? Node::process(const AnotherNodeA&, const AnotherNodeB&) seems to be a very generic description. It looks like you want something like for (each node in topological order) { node.process(node's predecessors); }? – Machado

Answer 1

You can use the Curiously Recurring Template Pattern.

For example, the user code would look something like this:

class MyNode {
  ...
};

class MyGraph {
  ...
};

class GraphInterface {
public:
  using Graph = MyGraph;
  using Node = MyNode;

  static Node* entry(const Graph& graph) {
    return graph.entry_node();
  }
  static Node* exit(const Graph& graph) {
    return graph.exit_node();
  }

  ...
};

Then your library code would be:

template <typename GraphInterface>
class GraphWalker {
  public:
    using Graph = typename GraphInterface::Graph;
    using Node = typename GraphInterface::Node;

  // Check template preconditions in the destructor
  ~virtual GraphWalker() {
    static_assert(...);
  }  

};

You can find an example of the library code for this pattern here and an example that uses that library code is here

(Don't dive too deep into those projects - they're not relevant to the problem, but those two links should give you a starting point for building what you need)

Ditto

Answer 2

It's not clear if these node types represent a single node in the DAG, that is, every node has a distinct type, or if there can be multiple nodes with the same node type, and the edge relationships are stored separately.

In the first case, the edges are defined implicitly by the typing, and topological depth can be determined in a constexpr way (Node<> has depth 0, Node<A, B, ...> has depth 1+max(A::depth, B::depth, ...)` etc.). The depth can be used to topologically sort heterogeneous collections of these nodes (however you choose to represent such collections).

In the second case, where there can be multiple nodes of the same type, there has to be a record of what the parent objects are — this can be held in a std::tuple member over (smart pointers or references to) the Input nodes. Again, it may not be necessary to have an explicit edge representation at all, unless they need to be labelled in some way. Either way, all nodes of type deriving from Node<> have depth 1, etc., just as in the one type per node situation, and this in turn gives the topological ordering.

Addendum: Another question is how the state, if any, of the DAG is represented. Does the DAG represent only a stateless process graph, to be evaluated over minimal-depth inputs? Or are nodes stateful? If the latter, is that state mutable?

Eudocia