关于javascript:有向无环图的模型设计与应用

从 TodoList 说起

对于咱们程序开发者来说，想要学习一个框架，从开发一个 TodoList 我的项目做起，这就像学习语言先学会写 Hello world 一样根底。但其实，简略的 TodoList 外面，同样能够蕴含一些简单的算法思维。

构想一下，明天须要实现若干个工作，须要布局一下工作流，能够通过 TodoList 记录下来。但与一般的线性工作不同的是，每条工作工作可能会有若干个前置工作，那么当初咱们该如何调配工作程序呢？

其实这样的事件在咱们本人平时的工作中常常遇到，而咱们通常的做法是：优先找出不须要做前置工作的工作，将其实现。再寻找剩下的工作工作中，是否有曾经将所有前置工作做完的工作，在接下来实现。如此往返，直到所有工作都曾经被实现。

事实上，人不知; 鬼不觉中，咱们曾经悄悄构建了一个有向无环图，并对其进行好了拓扑排序，依照拓扑序列的后果执行工作了。

有向无环图与拓扑排序

啥啥啥？我怎么不晓得？

你看，每一个工作与它的前置工作之间都存在着一个父子关系。因为每个工作的前置能够有多个，因而应用有向图而不是有向树来示意更为适合。而曾经做过的工作不会在被反复做一遍，因而工作流中不可能造成环路，从第一个工作开始，至最初一个工作完结，对于每个工作的执行必然是有且只有一遍的。而这，也就是有向无环图（Directed Acyclic Graph，下称 DAG 图）的定义了：

如果一个有向图无奈从某个顶点登程通过若干条边回到该点，则这个图是一个有向无环图。

而拓扑序列，实际上指的是一个 DAG 图的所有顶点的线性序列，行将一个二维图展平成一维链的一种示意模式。

并非所有有向图都能生成拓扑序列，咱们必须确保该图是不存在环的。

而查看有向图是否存在环的办法，咱们能够跟无向图一样，以深度优先遍历的形式查找图，并在遍历时对节点染色，以不便判断该节点是否已被拜访过。而其实，咱们能够间接应用拓扑排序算法来更直观的进行判断。

拓扑排序的具体方法如下：先统计所有节点的入度，找到一个入度为 0 的节点作为序列的第一个节点，将该点从图中删去，同时删去以该节点为弧尾的所有有向边，并将有向边指向的顶点入度减一，失去一个新图，之后反复以上操作。

举个例子，假如有这样一个 DAG 图，其拓扑排序的算法演示如下：

这样最终失去的拓扑序列为：

A -> D -> E -> B -> C

操作完结时，若未删去所有的节点，即呈现找不到入度为 0 的节点，则阐明残余的节点造成了一个环路，即该图有环，此时该函数就抛出谬误，存在循环援用，终止计算。

DAG 图数据模型设计

在理解了 DAG 图的工作原理之后，接下来咱们就能够撸起袖子开干了。

为了生成一个稳固的 DAG 图，首先咱们须要一个谨严的数据模型作为工程的撑持。咱们能够将我的项目的实现分为控制器与形成单元两个局部：

控制器局部负责 DAG 类整体的信息读取与写入，如查看布局信息，节点生成的拓扑序列，以及具体节点的增删改查等办法并在操作之后维持图的正确性，等等。

形成单元局部则绝对简略，负责寄存图中的自定义的顶点 node 以及关联关系 edge 的相干信息。

通过对这两局部的数据模型设计，即可形容一个残缺的 DAG 图的状态扭转关系以及查改任意一处的数据或关联关系了。于是咱们能够设计出一套根底且通用的数据模型，如下图所示：

图构造变动后依赖关系的修复

在上节数据模型中提到的 高级 API 对 DAG 图的操作中，都提到了一个子图的修复或重建行为，这也恰好是这个算法中的难点，值得独自抽出来简要说一说。

当咱们减少一个节点时，在设置好所有的邻边关系后，还须要对整图进行一次拓扑排序以排除存在环的可能。当存在环时，减少节点时增加的那条边可能会被弃用，以永远维持依赖图有向无环的稳定性。

当咱们删除一个节点时，会使得其该节点所关联的所有入度与出度生效，因而解决这种状况时，应该先去除该节点所有的入度，勾销掉对这些节点的监听，并沿着出度染色所有依赖该节点的继任节点，之后更新邻接表。

因为前置节点删除导致这些染色节点无奈实现本来的计算，因而也须要将这些染色节点进行革除解决（当然，染色节点是能够依据具体产品策略来判断是否须要保留的，如保留节点但存储的数据后果返回谬误）。

感觉比拟难以了解的话，咱们能够在下节的例子中实际一下。

在 Excel 中依赖图的利用

在 Excel 的设计中，函数性能是一个十分重要且难点极多的局部。设计函数性能，其中的难点在于：如何以代价最小的形式获取到该 Excel 函数所有依赖的数据，并能建设起对这些依赖数据的监听机制，在依赖数据更改时触发重算。

而对于这样简单且频繁的数据变更，显然应用一般处理事件的形式：订阅者模式是不实用的，咱们很难及时地进行事件的挂载与清理。

咱们晓得，在 Excel 表格中，一个单元格，既能够依赖多个单元格的数据，该单元格的运算后果也能够被多个单元格所依赖。并且当单元格之间造成了相互依赖时会报出循环援用 "#REF!" 谬误。

通过了之前的介绍，咱们很容易想到，函数的依赖关系恰好是合乎 DAG 图的个性的，因而咱们采纳该数据结构来存储表格内所有函数之间的依赖关系，称为表格的 依赖图。

依赖图中领有多个单元格中存储的数据作为图顶点，（当然，在 Excel 中作为顶点的能够是任何依赖图中其它顶点的自定义数据，以下对立称之为数据节点），这些顶点之间存在的依赖关系作为图的边。

当依赖图建设实现当前，咱们就可能解决任意一处的数据变更导致所有依赖节点的数据重算了。从变更的节点开始进行拓扑排序，按照生成的拓扑序列顺次重算所有继任节点，直到所有相干节点数据都被更新实现。

咱们来举一个例子，模仿一下计算机是怎么解决表格的依赖关系的。

如果有如下的一个 Excel 表格：

首先咱们来设计一下数据模型，在这个

他的依赖关系是什么样的呢，咱们能够很清晰地梳理进去。

再检查一下环，很好，合乎 DAG 图的定义，能够开始计算了。

先进行一次整表的拓扑排序，失去如下后果：

A1 -> A2 -> B1 -> SUM 函数 -> B2

接下来就能够顺次对每个节点进行计算了。因为每个节点计算所需的参数都曾经在前置解决中计算实现，因而每一个单元格的后果都是确定的。最终该 Excel 展示进去的后果如下，这样就帮忙 Excel 实现了一次依赖图建造与首次计算。

咱们也能够来试试用户操作对依赖图的影响。咱们能够看看把表格的 A2 单元格删除会产生什么。

依照之前所介绍的，当节点删除时同时也要删去其入度，变成下图这样：

接下来沿着出度对所有继任节点染色，B1 单元格、SUM 函数进入计算队列。

接下来遍历染色节点，因为这些节点处于依赖条件不满足，无奈计算的状态，依据 Excel 产品的策略，他们返回计算错误后果 #VALUE!。

（如果你在 Excel 中尝试了这个数据却发现没有呈现谬误后果，是因为 Excel 对空值做了默认解决，在数字计算时转化成了 0。）

之后更新他们的继任节点，依据拓扑排序后果，B2 单元格进入计算队列。因为 #VALUE! 的后果无奈失常参加计算，因而 B2 单元格也返回#VALUE!。最终 Excel 展现后果如下：

至此，Excel 的依赖图构造以及数据就实现了一次更新。

写在结尾

当然，在 Excel 中实在的依赖图架构的数据模型要比上节所介绍的简单得多。从节点的品种上，咱们可能须要辨别单元格节点、范畴节点、地位节点、函数节点、甚至各种各样的自定义节点，他们在接管图的变动时都有着不同的行为。在对图的操作上，也会多进去许多状况须要思考，如行列变更、复制粘贴、数据格式继承等等可能导致依赖图须要重算甚至重构的状况。

这里又能够细讲出很多篇文章，在此就不过多开展了，感兴趣的话能够在上节中根底的数据模型上自行扩大。

在简单的工程项目架构中，往往存在着大量精妙的算法设计。有向无环图的思路在 Excel 的设计中也只是其中一隅，下次我会介绍更多 Excel 中波及到的算法思路，帮忙大家意识适合的算法思维对简单问题的解决有多大的帮忙。

本文由博客群发一文多发等经营工具平台 OpenWrite 公布