有向图关键链路查找与分析

前言

好久没有写过东西了，加上傍晚的一杯奶茶，所以三点半爬起来敲敲键盘。正好最近看了一眼数据结构，来个旧货新整，讨论一下基于AOE网的评估算法，写到哪里算哪里，顺便将断更半年的博客续一续。

算法目的：

基于已经确定的、亦或已经发生的系统调度结果，分析当前的调度网络执行计划或日志。可以用于解析、评估计算机操作系统、道路交通系统、任务管理系统的调用效率与基础指标。

实现步骤：

1.分析数据输入：

我们这里先假设一个输入，它是任务执行的基础数据。将每一个任务抽象为一个单独的节点，节点内应该包含任务的基本信息，例如任务的UUID、执行权重（这里假设与执行时间相关）。

2.约束数据自由度与复杂性：

由计算机调度系统为例，任务的自由度体现在两个方面：一个是任务的执行时间，二是任务的执行核心。

由于多自由度需要的约束个数与其自由度应当匹配，其计算复杂度也随之上升，我们这里将约定单自由度的执行情况。即我们在预处理的时候，依据不同任务依赖的核心将任务预先分组，在一组中我们仅处理时间不同自由度的任务。

当然，由于后续要进行拓扑排序，这里需要将图确定为DAG图，方法就是使用DFS和广播搜索结合进行环路裁剪，这里实现与本文没有太大关系，之后单独再写。

3.依据业务内容，创建AOV网络

AOV（Activity On Vertex）网络，又称为活动节点图，是一种用于项目调度和关键路径分析的有向图模型。

我们简单的给出一些概念定义，这些定义会沿用到后面的AOE网络中：

顶点（Vertex）：在AOV网络中，每个顶点代表一个活动或任务，即项目中的一个具体工作单元。
有向边（Directed Edge）：顶点之间的有向边表示活动之间的依赖关系。如果存在一条从顶点A指向顶点B的边，这表示活动A必须在活动B开始之前完成。
依赖关系：AOV网络中的依赖关系定义了活动的逻辑顺序。常见的依赖关系包括：
- 完成-开始（Finish-to-Start, FS）：一个活动必须在另一个活动开始之前完成。
- 开始-开始（Start-to-Start, SS）：一个活动的开始依赖于另一个活动的开始。
- 完成-完成（Finish-to-Finish, FF）：一个活动必须在另一个活动完成之后才能完成，这种类型较少见。
入度和出度：
- 入度（In-degree）：指向一个顶点的有向边的数量。
- 出度（Out-degree）：从一个顶点出发的有向边的数量。
拓扑排序：AOV网络必须是一个有向无环图（DAG），这意味着可以对顶点进行拓扑排序，即找到一个顶点的线性序列，使得对于任何一条有向边(u, v)，顶点u都在顶点v之前。
最早开始时间（Earliest Start Time, EST）：在满足所有依赖关系的条件下，一个活动可以开始的最早时间。
最晚开始时间（Latest Start Time, LST）：在不推迟整个项目完成的前提下，一个活动可以推迟开始的最晚时间。
关键路径：项目中最长的活动序列，其上的活动称为关键活动。关键路径的长度决定了项目的总工期。任何关键活动的延迟都会影响整个项目的完成时间。

我们给出如下的节点代码定义：

struct EventNode {
    uuids::uuid node_id; // 事件的唯一标识符
    uint64_t node_weight; // 事件的权重（可以映射到执行时间或者whatever）
    std::vector<ActivityEdge*> outgoing_edges; // 出发边列表
    std::vector<ActivityEdge*> incoming_edges; // 进入边列表
};

同时，我们给出DAG图的定义：

EventNode* createEventNode(uint64_t node_weight) {
    EventNode* newNode = new EventNode;
    newNode->node_id = uuids::uuid_generator()(); // 生成新的uuid
    newNode->node_weight = node_weight;
    return newNode;
}

void addDependency(EventNode* before, EventNode* after) {
    before->successors.insert(after);
    after->predecessors.insert(before);
}

构建AOV的示例：

int main() {
    // 创建活动节点
    EventNode* A = createEventNode(3);
    EventNode* B = createEventNode(4);
    EventNode* C = createEventNode(5);
    EventNode* D = createEventNode(2);
    EventNode* E = createEventNode(1);

    // 添加依赖关系，构建DAG
    addDependency(A, C); // A完成后C开始
    addDependency(B, D); // B完成后D开始
    addDependency(C, E); // C完成后E开始
    addDependency(D, E); // D完成后E开始
    std::cout << "Activities in AOV Network:" << std::endl;
    std::cout << A->uuid_id << " - Duration: " << A->duration << std::endl;
    std::cout << B->uuid_id << " - Duration: " << B->duration << std::endl;
    std::cout << C->uuid_id << " - Duration: " << C->duration << std::endl;
    std::cout << D->uuid_id << " - Duration: " << D->duration << std::endl;
    std::cout << E->uuid_id << " - Duration: " << E->duration << std::endl;

    // 清理内存
    delete A;
    delete B;
    delete C;
    delete D;
    delete E;

    return 0;
}

4.修改数据结构，将其代入AOE网的基础格式

AOV网更侧重于活动之间的逻辑顺序，而AOE网则提供了一种更为全面的分析方法，包括活动的持续时间和关键路径的确定。这里的核心原因在于以节点为中心且不限制节点连接（多个出边和入边）的网络过于复杂，无法合理的归纳和整理为算法。

由于AOE网的关键点在边，所以需要加入活动边的定义：

struct ActivityEdge{
	uuid edge_id;
	uint64_t edge_weight;
	EventNode * node_start;
	EventNode * node_end;
}

下面，我们需要一些简单的转换，规则是将节点的持续时间关联到边的权值，并且边的权值定义为到达下一个节点需要的时间。

ActivityEdge* createActivityEdge(EventNode* start, EventNode* end, uint64_t duration) {
    ActivityEdge* newEdge = new ActivityEdge;
    newEdge->edge_id = end.uuid;//边的uuid与后继节点一致，用于关联权值
    newEdge->node_start = start;
    newEdge->node_end = end;
    newEdge->edge_weight =newEdge->node_end->node_weight;   
    return newEdge;
}

当然，在进行以上转换之后，我们会发现一个问题，就是有的节点没有入度，就无法将自己的权重赋值到前一个边上，针对这样的情况，我们需要引入虚拟节点，虚拟节点的入度和权重都为零，作用仅仅是承接后一个节点的执行权重。

5.拓扑排序，求解事件的最优、最坏时间与活动的最优、最坏时间

ok，现在正式开始计算的部分，首先，仍然定义几个概念：

事件节点：

整张调度图表中需要执行的事件，含有执行依赖关系、执行时长。

活动节点：

整张调度图表中需要执行的事件过程，代表一种运行事件的状态，含有信息与事件节点类似。

节点有序性：

节点之间有执行的关系依赖性，即A做完了才能做B，油烧热了才能下肉；所以我们需要一个能进行先后排序的算法，即拓扑排序。

事件、活动的最早、最晚执行时间：

由于图表的特性，相同约束的情况下可以有多个并行解，每个解中每个事件、任务的执行时间会有差异，所以有最早、最晚的区别；

同时，由于关键链的存在代表整体调度的特征，若关键链不被有效约束，将导致整体调度效果的偏差，所以我们这里需要在关键路径上求解最坏路径。

以下是部分计算伪代码：

拓扑排序:

// 拓扑排序函数
std::vector<EventNode*> topologicalSort(const std::vector<EventNode*>& nodes) {
    std::vector<EventNode*> sortedList;
    std::queue<EventNode*> zeroInDegreeQueue;

    // 初始化入度
    for (auto node : nodes) {
        node->in_degree = node->incoming_edges.size();
        if (node->in_degree == 0) {
            zeroInDegreeQueue.push(node);
        }
    }

    // 拓扑排序算法
    while (!zeroInDegreeQueue.empty()) {
        EventNode* node = zeroInDegreeQueue.front();
        zeroInDegreeQueue.pop();
        sortedList.push_back(node);

        // 减少以当前节点为终点的边的起点节点的入度
        for (ActivityEdge* edge : node->outgoing_edges) {
            EventNode* startNode = edge->node_start;
            if (--startNode->in_degree == 0) {
                zeroInDegreeQueue.push(startNode);
            }
        }
    }

    if (sortedList.size() != nodes.size()) {
        std::cerr << "Graph has cycles, cannot perform topological sort." << std::endl;
        exit(-1); // 或者其他的错误处理方式
    }

    return sortedList;
}

最早、最晚执行时间计算

首先，我们将每一个节点设置一个结构体，用来存贮计算迭代值

struct node_caculate{
	uuid id;
	int ve=0;
	int vl=0;
}

在所有节点中，初始值都为零。由于我们之前经历过DAG图的转换和虚拟节点的添加，我们这里统一由虚拟节点出发，按拓扑序所有节点使用广播的方式，将活动边的代价传递给后续节点（每次传播仅考虑自己的ve和自己指向下一节点的cost），这里需要注意的是，在广播、更新ve值的过程中，我们使用取大值的原则。更新完所有节点之后，我们就计算完了所有的ve（最早开始时间）。

接下来就是最晚开始时间vl的求解了，首先，对于拓扑序的终点，ve=vl，这个没有什么好解释，毕竟关键路径是需要定死开始时间与结束时间的。

然后，将所有节点都初始化为这个值，也就是整个调度的最晚执行时间，这里方便我们之后更新数据。

接着，使用逆拓扑序，从最后一个节点出发，以反向的指向进行广播，用于更新vl，同理，在更新的过程中我们取最小的值作为最晚开始时间，用于保证整体调度可以被完成。

至此，所有节点的ve、vl均已计算完毕。

事件的最早最晚已经计算完毕，接下来就是活动的最早与最晚执行时间了。此时，我们将活动的最早开始时间等同于前驱节点的最早开始时间，将活动的最晚开始时间定义为后继节点的最晚开始时间减去cost。

至此，所有活动的ve、vl均已计算完毕。

6.分析求解关键事件与关键链路

关键路径为调度表的最长执行路径，具有代表调度表特征的作用，在完成所有节点的计算之后，ve=vl的所有活动，都是关键活动，这些活动构成的线路，就是关键路径。

关键路径可能不止一条，此时就需要下一步来进行统计和归纳。

7.统计关键链路与关键事件信息，获取统计特征

路径长度：计算每条关键路径上的活动持续时间之和。
活动数量：统计每条关键路径上的活动数量。
资源消耗：分析每条关键路径上的资源消耗与时间的分布情况。
浮动时间：非关键路径的活动浮动时间。
风险评估：对每条关键路径进行风险评估。
关键活动：关键活动的时间分布与资源消耗情况。
路径依赖性：分析关键路径之间的依赖关系，路径之间的关系。
项目总浮动时间：计算整个项目的总浮动时间，评估项目整体的时间弹性。
关键路径的分布：分析关键路径在项目网络图中的分布，了解关键路径是否集中在特定阶段或区域。
项目缓冲策略：基于关键路径分析，制定项目缓冲策略，以应对潜在的延误。

8.多核多任务分析：

未完待续

类似思路的应用示例：

Aoe网络到多叉树结构的异构转换方法 CN104182499A

沈敬伟, 周廷刚, 张弘弢. 基于改进AOE网络的低频浮动车数据地图匹配算法[J]. 西南交通大学学报, 2015, 28(3): 497-503. doi: 10.3969/j.issn.0258-2724.2015.03.018

参考文献：

Q.E.D.

前言