C++数据结构的拓扑排序

Question

在开始之前，我首先要提到 "graph" 这个词指的是显示结构的图像。由于我的视力障碍，我无法想象也无法画出它们。我可以看着它们并理解 - 但我很难自己编造它们。

我正在开发一个构建工具，该工具使用脚本语言生成目标，这些目标被处理并拆分为任务。任务表示为数据结构：https://github.com/IngwiePhoenix/IceTea/blob/master/src/main.cpp#L98

如你所见，Task class 注意到它是一个母版（过程的实际结果）并存储一个引用 - 注意，仅一个引用，而不是数组- 其 child 和 parent - 如果有的话。

到目前为止，我能够用所有需要的任务填充任务队列并将其发送到执行器void Run(void*)：https://github.com/IngwiePhoenix/IceTea/blob/master/src/main.cpp#L1107

但是问题来了：

任务没有正确排序，如果之前的构建被取消然后重新开始，构建将变得一团糟。如果您有 a.cpp 和 b.cpp，并且您的最后一次构建在其中一个终止而另一个未构建，则会导致 parent 任务被运行两次。一种适当的排序机制——一种拓扑机制——很可能会解决这个问题。现在，我已经 class 将其定义为 non-existent 依赖项跟踪。
当一个目标依赖于另一个目标时，依赖于另一个目标的目标最终可能会在队列中在它所依赖的目标之前。假设您有 libfoo.a 和 bar.exe。编译 bar.exe 的任务可能在创建 libfoo.a 的任务之前发生。这意味着，我们运行会出现链接错误。

目前，该程序由一个线程池构成，该线程池从队列中提取任务并运行发送它们。但是在我对 Ninja 工具进行更多调查之后，这种逻辑可能会改变；将有一个线程池只执行从脚本语言生成的命令。然而，这必须等待，现在。因此，我只在单个线程上制作工具运行，以模拟我真正想要的行为；一个命令运行一个又一个。

我主要面临的问题还是排序机制。根据我对构建工具的研究，他们倾向于使用所谓的 DAG 和拓扑排序。现在，我既找不到关于如何编写拓扑排序算法的很好的解释，也根本不知道它是如何工作的。我知道有常数 u 和 v。但是我找不到实现它的方法。

至此，我明白了它是一个线性图。让我们假设以下结构：

myApp.exe
    - main.o
    - util.o
    | libfoo.a
        - foo_a.o
        - foo_b.o

这很简单。有一种结果，一种依赖。但是，如果我们有两个结果取决于同一个 libfoo 怎么办？

myApp.exe       libbar.so
    - main.o        - barlib.o
    - util.o        
-------------------------
            | libfoo.a
                - foo_a.o
                - foo_b.o

这就是我已经停滞不前的地方。

您能否向我解释一下如何实现拓扑算法，以及 DAG 实际上是什么？这真的很有帮助，因为老实说，我在这里遇到了一个难以克服的障碍。提前致谢！

A side-note：我希望工具尽可能小，因此我不能添加像 Boost.Graph 这样的东西，我已经看到它作为搜索结果。

Answer 1

好吧，首先要做的是：DAG 是 D 有向 A 循环 G拉夫。

图是一种数据结构，其中的节点相互连接某种方式。例如，地图是一个图形，其中交叉点是节点和道路是边缘。
有向图是边上有某种方向的图；例如，许多道路是无方向的（请留在正确的路边），但有些是 one-way.
无环图是没有任何循环的图；这意味着一旦你离开一个节点，你就无法回到它。

您无法对循环图进行排序；循环的哪一部分会先出现？但是您可以对非循环图进行排序，结果是 'topological sort.' 正如您在第二个示例中指出的（可能是不小心），多个拓扑排序可能对同一个图有效。

为了处理问题中的依赖关系，您将使用图表。但是，由于您知道它将是非循环的，因此您可以编写自己的非常简洁的图形 class。

struct node {
  string name;
  vector<node*> out_neighbors;
  vector<node*> in_neighbors;
}

您可以将所有节点存储在一个数组中，graph，并且节点在 out_neighbors 中保留它们之后的节点列表（这称为 "adjacency list"格式）。

现在你如何对它们进行排序？好吧，您希望对它们进行排序，以便节点不依赖于稍后出现的节点。首先，您想找到所有没有传入边的节点（即不依赖于任何东西）。

queue<node*> free;
for(int i=0; i<n; ++i)
  if(graph[i].in_neighbors.size() == 0)
    free.push(&graph[i]);

接下来，您将使用这些来查找其他节点。

queue<node*> topsort;         //this is going to be the sorted nodes
while(free.size() > 0) {
  node* top = free.front();   //remove the first element from the graph
  topsort.push(top);
  free.pop();

  for(int i=0; i<top->out_neighbors.size(); ++i) {
    node* neighbor = top->out_neighbors[i];
    neighbor->in_neighbors.erase(
      find(neighbor->in_neighbors.begin(), neighbor->in_neighbors.end(), top)
    );
    if(neighbor->in_neighbors.size() == 0)
      free.push(neighbor);
  }
}

最后，topsort 将是按拓扑顺序排序的节点指针列表。但是，所有传入边也已从图中删除（这可以使用传出边轻松重建）。

一些建议：

首先，你的Task已经和我这里描述的简单结构一样了，只是它们只有一个parent和child指针；为什么不列出 parents（传入）和 children（传出）？然后你可以对 Task objects 自己进行排序。

其次，一旦按拓扑排序，就可以运行线程中的东西；只要我所有的传入边缘都已编译，我也可以自由离开。

C++数据结构的拓扑排序

Topological sorting of C++ data structures

c++

sorting

algorithm

multithreading

graph