DataStructure Graph AOE and AOV Network

Introduction

在本文，我们将会介绍两种DFS算法的基本应用：AOV网络和AOE网络

AOV

我们假设一个工作流如下：

我们定义一个原子化任务为$T_k = \\{ A_k, S_k \\}$，其中$S_k \subseteq \bigcup \\{T_i \\}$代表前置任务的集合。

在访问$T_k$之前，需要满足以下的前提条件：

$$\forall x \in S_k(x \text{ is visited.})$$

AOV网是对现实工作的真实建模，不同的工作之间往往存在先后之分。例如，你需要在学习数据结构之前学习程序设计。

如何根据工作流建立数据结构？很显然，我们可以使用拓扑排序和深度优先搜索来实现！首先，我们需要保证图是有向无环图，因为我们需要建模的是不同节点之间的依赖关系。

建模之后示例如下：

可以看到有向边代表的信息是不同节点之间的继承关系，而每个节点表示具体的原子任务，上文建模中的$S_k$就是对应节点的所有first endpoint组成的集合，也就是入度。因此，我们把这种网络叫做 Activity on Vertex Network (AOV Network).

拓扑排序

如何实现拓扑排序？

• 首先找到一个入度为0的点。
• 入度为0可以形象地概括为这个节点的全部预备先修节点已经被访问了，逻辑上的
  • 从这个节点开始，访问该节点。
  • 在逻辑上删除它和从它出发的所有边。
  • 对它的后继检查入度是否为0。
  • 如果其后继存在入度为0的点，继续push进入队列。
• 如果队列为空但是并没有遍历完全，说明节点存在环，不符合有向无环图的定义。

时间复杂度：$O(|V| + |E|)$

一般来说，线性的图论算法如果使用邻接表存储可以达到$O(|V| + |E|)$的时间复杂度，如果使用邻接矩阵存储可以达到$O(|V|^2)$的时间复杂度。

• 如果为稀疏图，$|V|$很大但是$|E|$很小，此时邻接矩阵会存在严重的空间浪费问题，因此使用邻接表储存更方便。
• 如果为稠密图，$|V|$很小但是$|E|$很大，那此时邻接表的存储是非常高效且简单的，反而邻接表的使用更加的复杂。

AOE

In contrast, we have Activity on Edge Network (AOE Network) as follows:

顾名思义，我们此时需要把活动定义在有向边上，而不是在节点上。

我们假设在一个工作流存在若干个时刻，$t_0,t_1, t_2, t_3, \cdots,t_n$.这里只考虑离散化的时刻。我们把第一个时间节点定义为源点($t_0$), 把最后一个时间节点定义为$t_n$，即汇点。

• 我们允许并行事件的发生

• 但是和AOV一样，事件之间存在严格的先后关系。

• 将活动定义在有向边上，而不是定义在节点上。

• 顶点代表事件，而有向边的权值代表某个活动的持续时间。有向边的方向代表事件先后的发生次序。

AOE网的关键：遍历所有节点的最长时间，以及那些节点事件是影响工程进度的关键事件。

因为我们允许时间并行，因此从源点到汇点的最长时间就是完成工程的最短时间。（当最长路径上的活动完成之后，其他路径长的活动肯定已经完成）

这貌似是一件很荒谬的事情，不过是正确的。

我们来看上面的图，把$t_0$作为源点，$t_3$作为汇点，我们的任务是要在尽可能的短的长度内遍历图上所有的点（允许并行）。

很显然，从起点到终点的最短路径长度为2，即走最下方的那条路。但是问题在于此时达到汇点之后需要等待上游两条路结束，此时我们的任务还没有完成。

我们可以理解为我们需要等最慢的支路完成了，此时才可以认为整体的支路完成了。

因此，我们就可以明确我们的目标：求从起点到终点最长的路径。

Given the starting point $x$ and the ending point $y$, we need to find the longest path from $x$ to $y$. (Practically, it means the worst situation of an event). We call it a critical event.

更新的算法也很简单，使用类似于动态规划的思想：

$ee(v_i) = \max \\{ ee(v_k) + L_{k,i} \\}$

使用一次DFS遍历，不断更新下一个节点的最长长度。

不过同时，我们还需要计算顶点的最迟发生时间，转化一下就是如果我们倒着看，就是从终点向起点的最长发生时间。（在我们已知收点的最迟发生时间的情况下），按照逆拓扑序的顺序找到最小值。

如果最早发生时间 == 最迟发生时间，说明这个节点很关键（被卡脖子了）。