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

Question

我正在寻找有关如何使用模板在 C++ 中实现 DAG 的建议。主要思想是设计一种框架，用户可以使用自己的类（节点）对其他节点提供的输入执行一些工作。鉴于类之间的这种关系，DAG 似乎是一个自然的选择。同时，我想避免依赖虚拟抽象接口，因为我认为用户实现带有明确说明所有所需输入的签名的工作方法会更清楚，例如，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;
}

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

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

NodeA
        Node1
                NodeX
                NodeY
NodeB
        Node2
                NodeX
        NodeY

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

Answer 1

目前尚不清楚这些节点类型是否代表 DAG 中的单个节点，即每个节点都有不同的类型，或者是否可以存在多个具有相同节点类型的节点，并且单独存储边关系。

\n

在第一种情况下，边是通过类型隐式定义的，并且拓扑深度可以以 constexpr 方式确定（Node<>深度为 0，Node<A, B, ...>深度为 1+max(A::深度，B::深度，...)` ETC。）。深度可用于对这些节点的异构集合进行拓扑排序（但是您选择表示此类集合）。

\n

在第二种情况下，可以有多个相同类型的节点，必须有一个父对象是什么的记录 \xe2\x80\x94 这可以保存在一个std::tuple成员中（智能指针或引用）输入节点。同样，可能根本不需要有明确的边缘表示，除非需要以某种方式标记它们。无论哪种方式，派生类型的所有节点都Node<>具有深度 1 等，就像每个节点一种类型的情况一样，这又给出了拓扑排序。

\n

附录：另一个问题是 DAG 的状态（如果有）如何表示。DAG 是否仅代表一个无状态流程图，要通过最小深度输入进行评估？或者节点是有状态的吗？如果是后者，该状态是可变的吗？

\n