c++ - 如何在 C++ 编译时实现有向无环图 DAG

Question

我正在寻找有关如何使用模板在 C++ 中实现 DAG 的建议。主要思想是设计一种框架，用户可以在其中带上自己的类(节点)来对其他节点提供的输入执行一些工作。鉴于类之间的这种关系，DAG 似乎是一种自然的选择。同时，我想避免依赖虚拟抽象接口(interface)，因为我认为用户更清楚地使用签名明确说明所有必需的输入来实现工作方法，例如Node::process(const AnotherNodeA&, const AnotherNodeB&)而不是 Node::process(const set<AbstractNode*>&) .
我想我想出了如何使用类型列表来实现类型的层次结构。例如，下面实现了一个像这样的简单图表:

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

上面打印了定义类型的层次结构:

NodeA
        Node1
                NodeX
                NodeY
NodeB
        Node2
                NodeX
        NodeY

会 std::pair<ChildNode, ParentNode>是实现节点之间“边缘”的好选择，即 ChildNode -> ParentNode ?可以使用一组这样定义的对来验证和/或对节点进行拓扑排序吗？

Answer 1

目前尚不清楚这些节点类型是否代表 DAG 中的单个节点，即每个节点都有不同的类型，或者是否可以有多个节点具有相同的节点类型，并且边缘关系单独存储。
在第一种情况下，边缘由类型隐式定义，拓扑深度可以通过 constexpr 方式确定(Node<> 深度为 0，Node<A, B, ...> 深度为 1+max(A::depth, B::depth , ...)` 等)。深度可用于对这些节点的异构集合进行拓扑排序(但是您选择表示此类集合)。
在第二种情况下，可以有多个相同类型的节点，必须记录父对象是什么——这可以保存在 std::tuple 中。成员(智能指针或引用)输入节点。同样，可能根本不需要明确的边缘表示，除非它们需要以某种方式标记。无论哪种方式，所有类型的节点都来自 Node<>具有深度 1 等，就像每个节点一种类型的情况一样，这反过来又给出了拓扑排序。
附录:另一个问题是如何表示 DAG 的状态(如果有)。 DAG 是否仅代表一个无状态过程图，在最小深度输入上进行评估？或者节点是有状态的？如果是后者，该状态是否可变？