一种基于有向无环图的依赖管理机制及实现*

颜 雨，李洋昕，张咏秋

（1.海军装备部，四川 成都 610036；2.中国电子科技集团公司第三十研究所，四川 成都 610041）

0 引言

控制类软件通常需要维护大量的状态信息，根据输入数据推动内部状态机运转，从而输出控制信息。这些内部状态信息之间通常包含复杂的依赖关系，一个输入条件的改变会引起内部一系列的连锁反应。如果这些状态以及状态之间的关系都采用硬编码，状态依赖关系处理会分散在软件代码各处，正确性完全依赖于实现人员，易出现偏差，且后期软件的维护工作会非常困难。当依赖关系稍有变动，软件就需要做较大改动，易有所遗漏。

图论以图为研究对象。研究的图是由若干抽象的点以及若干连接两点的线所组成。在实际应用中，通常可以用点代表事物，连线代表两个事物之间的关系，以此研究处理多个事物间的复杂关系[1]。

本文针对大量状态之间的复杂依赖关系问题，基于图论中的有向无环图相关理论，把软件中的每一个状态信息抽象成一个点，两个状态之间的依赖关系抽象成这两个点之间的有向线段，把复杂状态依赖问题抽象成对有向无环图问题的求解[2]。

1 需求分析

控制软件的主要功能是根据系统输入信息以及系统当前的状态做出控制决策。系统输入信息包括设备时钟或定时器、系统数据输入、系统传感器输入以及用户输入等。系统状态包括系统内部数据状态、系统软件运行状态等。控制软件在处理系统外部输入时，需先要根据预定的逻辑推动内部状态机运转，修改系统内部状态[3]。控制软件内部通常会包含多个状态机，分别处理不同子系统的逻辑。多个状态机之间彼此推动运转，直到达成一个稳定状态。在状态机运转的同时，根据状态机设定执行预定操作，输出控制决策。同样的，对于外部输入，当系统状态不同时，系统做出的控制决策也不尽相同。

控制软件通常需要面对一个复杂系统，软件内部需要维护大量的状态信息，以便精确与实际环境相对应。数量众多的状态之间相互依赖，关系盘根错节，增加了控制软件的复杂度，严重威胁软件的可靠性。目前，比较常用的简化问题的方法是把全部状态集合划分成若干个较小的子集合。每个子集合规模不大，内部状态关系相对清晰[4]。跨越子集合的状态依赖关系归结为子集合之间的依赖关系。这样实际上就把原始问题划分成了两个层次，一是子集合内部问题，二是子集合之间的问题，降低了问题规模，间接提高了软件实现的正确性。

虽然通过上述方法可以降低软件实现难度，但是并没有解决软件正确性全部交由实现人员保证的问题，且仍然存在软件可维护性基础较差、无法灵活面对需求变更的问题。本文应用图论中的有向无环图理论，设计并实现了一套依赖管理机制，把系统内状态信息抽象成点，状态信息之间的依赖关系抽象成有向边，每个状态点仅需要关注有依赖关系的少数状态点，简化了问题规模，通过有向无环图的相关算法自动解决状态信息之间的依赖传递问题。

2 算法设计

首先需要构建生成系统状态信息组成的有向图，初始化有向图各顶点的基本状态，然后可以接收处理外部输入，修改内部状态，通过遍历有向图传播内部状态变动，输出控制指令。

2.1 初始化

2.1.1 建立有向图存储

有向图的建立主要是生成顶点和有向边信息。信息可以从配置文件加载，也可以把构建过程固化在软件代码中。有向图在算法中采用双重邻接表的结构存储。普通邻接表为图中的各个顶点独自建立一个链表，链表中存放所有直接可达的顶点，即是以该顶点为起始点的有向边的终止顶点。双重邻接表在邻接表的基础上为每个顶点增设了一个链表，存放所有逆向直接可达的顶点，即是以该顶点为终止顶点的有向边的起始顶点。双重邻接表实质上分别以起始顶点和终止顶点为线索，把有向边保存了两次，方便从正向和逆向遍历有向图。

每个顶点在实现上使用state_vertex 类来保存。类定义如下：

需要说明的是，state 成员表示顶点的当前状态，initted 成员表示节点顶点状态是否经过初始化，edges_in 存储逆向直接可达顶点，edges_out 存储直接可达顶点。

2.1.2 加载状态

完成有向图存储的建立后，需要加载各个顶点的初始状态。由于各个顶点代表的实际状态有很多类型，部分顶点有外部真实状态相对应，可以在初始化时确定状态值。部分顶点只代表了软件的一个中间状态，需要根据其他顶点的状态动态计算实际的状态值。顶点状态初始化的第一步是独立计算各个顶点的状态值。

对于无法独立确定状态值的顶点，采用默认的load_state 方法设置初始状态值。load_state 方法定义如下：

需要说明的是，设置initted 成员为false，表示该顶点的状态值没有最终确定。对于可以独立确定状态值的顶点，则需要根据具体情况重载该方法，为state 成员设置合适的取值，并将initted 成员设置为true，表示该顶点的状态值已经最终确定。

2.1.3 进入稳定状态

完成状态加载后，由于部分中间状态还没有确定，需要计算确定这部分顶点的状态值后，有向图才能进入稳定状态发挥功效。中间状态节点的状态值由该顶点的逆向直接可达顶点的状态值共同决定。check_depends 方法用于完成这一功能。该方法遍历了指定顶点的edges_in 列表，检查是否列表中的所有顶点状态值都是true，如果是则返回true，否则返回false。如果其中有顶点的initted 成员是false，则抛出异常。check_depends 允许顶点重新定义，采用更加个性化的状态值计算方法，定义如下：

由于中间状态顶点可能存在嵌套依赖的现象，一次遍历不一定能计算出所有中间状态顶点的状态值，因此需要采用多轮遍历。如果某一次遍历成功得到状态值的顶点数为0，则表示出现了无法确定初始值的中间状态顶点。这表示有向图的设计有问题，需要重新安排各个顶点的类型与连通关系等。完整的有向图初始化函数实现如下：

2.1.4 示 例

下面以一个远程访问流程控制为例，简述有向图的初始化过程。远程访问过程需要用户设置目标服务器的IP 地址和端口，以及用于身份认证的用户名和密码信息。根据软件控制流程，建立如图1所示的有向图。

“IP 地址”“端口号”“用户名”和“密码”4个顶点与配置信息内容高度相关，初始化时根据配置项是否加载成功设置状态。“连接信息”是“IP地址”和“端口号”状态的汇总，便于软件衡量是否具备建立连接的基础，属于中间状态，需要等待其他顶点状态加载完成后，通过自身的check_depends 方法计算状态值。“登录信息”同样属于中间状态，需要通过自身的check_depends 方法计算状态值。“连接状态”和“登录状态”是软件的动态状态，需要自定义加载状态方法，设置初始状态为false。

图1 有向图初始化

2.2 处理外部输入

有向图进入稳定状态后，可以开始处理外部输入。外部输入信号经过处理后最终会造成某个顶点的状态值产生变化。该顶点处理完自身状态变动后，将沿着有向边向直接可达的顶点发起通知信号。收到该信号的顶点由于输入依赖的状态值有变化，需要重新计算并更新自身的状态值，并继续沿着有向边传播通知信号，直到整个有向图达成一个新的平衡。

外部信号通过调用顶点的set_state 方法改变顶点的状态值，其中使用到的change_state 是一个可重载的方法，默认实现是直接返回新状态值，通过重载可以实现对输入信号的个性化处理。

顶点之间传递通知信号，使用当前顶点的broadcast 方法在broadcast 方法中遍历需要接收信号的顶点，并调用其activate 方法，实现信号的传递。

基于如图2 所示的有向图，当顶点A 的状态改变时，会发生以下一系列方法调用：

（1）设置A 的状态：A.set_state；

（2）A 自身状态变更：A.change_state；

（3）A 向外通告状态变化：A.broadcast；

（4）B 被激活：B.activate；

（5）B 检查自身依赖满足情况：B.check_depends；

（6）B 自身状态变更：B.change_state；

（7）B 向外通告状态变化：B.broadcast；

（8）C 被激活：C.activate；

（9）C 检查自身依赖满足情况：C.check_depends；

（10）C 自身状态变更：C.change_state；

（11）C 向外通告状态变化：C.broadcast。

顶点可以重载change_state 方法，自由控制顶点的状态转换过程。

图2 有向图顶点关系示例1

2.2.1 拓扑排序

如果通知信号不加区分的向所有直接可达顶点发送，部分顶点会重复收到通知消息，产生不必要的处理。为了避免这种情况，需要对顶点进行拓扑排序，确保所有需要接收通知信号的顶点能够按顺序处理，且不会重复收到消息。

这里的拓扑排序只针对完整有向图的一个子区域从最初受影响的顶点开始，范围包括其他所有可达的顶点，此外的顶点不参与拓扑排序。由于拓扑排序的对象是有向图的部分子图，常用的每次删除入度为0 的拓扑排序算法并不适合，这里借助深度优先的遍历方法实现部分区域的拓扑排序，代码实现如下：

基于如图3 所示的有向图，顶点A 状态改变，将会依次通告B、D、C。B 会通告D，D 会向C发起第二次通告。这样就有重复的通告过程。通过以顶点A 为起始顶点做拓扑排序，排序结果为A →B →D →C。当A 状态改变时，只需要依次向B、D、C 发起通告即可，降低了通告过程的复杂度。

图3 有向图顶点关系示例2

2.2.2 激发处理

顶点通过重载change_state 方法，可以自定义状态值改变时执行的操作。此时，可以根据操作结果选择保持当前状态值或者改变状态值。在change_state 方法中，还可以根据当前状态对外部做出控制指令，实现控制软件对外部的控制输出。

2.2.3 剪 枝

在单向图传递通知信号时，部分顶点可能会选择不改变当前状态值，后序遍历的顶点可能会出现所有逆向直接可达顶点的状态值都没有改变。此时，为了优化控制软件的运行速度，可以选择不再向后发送通知信号，减少触发操作，提高处理效率[5]。

2.3 逆向遍历

根据外部输入，沿着有向边传递通知信号，属于有向图的正向遍历。还可以对有向图进行逆向遍历，确定某个顶点的目标状态值逆向回溯有向边，主动创造达成目标状态的条件，或者检查达成目标还有哪些中间条件需要得到满足。

2.4 优 化

有向图的遍历还有一定的优化空间，最直接的就是以空间换取时间，保留每个顶点的拓扑排序结果，后续该顶点状态改变时，就不再需要进行拓扑排序过程，减少了计算步骤。

3 结语

本文使用有向图理论解决大量复杂依赖关系管理的问题，将状态信息抽象成顶点，将状态信息之间的依赖关系抽象成有向边，通过求解对应有向图的问题，实现了状态信息之间的自动推导管理。这种方法相比硬编码依赖关系更加可靠，且可以实现状态信息和依赖关系的动态加载，实现了逻辑关系与软件实现的相分离。