背景
在我们app开发中，总会遇到各种各样的需要初始化的任务，各个任务又会有各种前后依赖，那么我们怎么办！手动添加依赖关系，肯定会导致后期依赖成本过大，所以我们肯定会引入各种各样的框架去解决这个问题。那么我们今天就来动手实现这么一个框架！
目标
我们要完成的目标是：
- 支持Task自动依赖转化，即我们要实现无论我们任务如何定义，只要声明了任务的依赖关系，就能自动处理好任务之间的处理关系
- 支持任务循环依赖检测，即我们任务如果存在循环依赖，那么就要给出相关的提示
拓扑算法
这里我们开始引入一个小算法了，就是拓扑排序算法（对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。）好啦，我们看了完全不知道啥意思的官方解说，我们直接看下图吧！
1.png
可以看到上图，简单来说，拓扑算法就是 把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的
拓扑排序有很多种实现的方式，比如BFS （广度优先遍历），DFS （深度优先遍历），这里咱们用BFS的方式实现
基于 BFS 的拓扑排序算法的步骤如下：
- 计算图中每个节点的入度：遍历所有边，统计每个节点的入度（即指向该节点的边的数量）。
- 创建一个队列，将所有入度为 0 的节点加入队列。这些节点没有前驱节点，可以立即处理。
- 进入循环：当队列非空时进行如下操作：
a. 从队列中取出一个节点，将其添加到拓扑排序的结果列表中。
b. 遍历以此节点为开头的所有边，将边的终点的入度减 1。如果边的终点入度变为 0，则将其加入队列，表示可以处理此节点。
c. 删除此节点及其边。
- 如果结果列表中的节点数量与图中节点数量相同，则说明所有节点都被处理，拓扑排序成功。如果不相同，说明图中存在环，拓扑排序失败。
通过上述的算法，我们就能实现目标1的内容了，接着，我们还有目标2，怎么去实现检测到环并且给出具体的节点呢？我们可以利用步骤b的时候，减少入度的这个条件，我们就可以知道，当发生环的时候，肯定会存在入度不为0的节点，而这个节点，就是我们需要的环节点！
直接看代码
val indegree = hashMapOf<ITask, Int>()
val queue = LinkedList<ITask>()
val cycleNodes = mutableListOf<ITask>()
计算所有节点的入度
taskGraph.keys.forEach { it ->
taskGraph[it]?.forEach { itask ->
indegree[itask] = indegree.getOrElse(itask) { 0 } + 1
}
}
taskGraph 是一个图的邻接表实现
taskGraph.keys.forEach {
if (indegree.getOrElse(it) { 0 } == 0) {
queue.offer(it)
}
}
var count = 0
val result = mutableListOf<ITask>()
进入BFS
while (queue.isNotEmpty()) {
val node = queue.poll() ?: break
result.add(node)
count++
taskGraph[node]?.forEach {
indegree[it] = indegree.getOrElse(it) { 1 } - 1
if (indegree[it] == 0) {
queue.offer(it)
}
}
}
环检测
if (count != allTaskSet.size) {
for (entry in indegree) {
if (entry.value > 0) {
cycleNodes.add(entry.key)
}
}
throw java.lang.RuntimeException("find cycle dependents $cycleNodes")
}
return result
（ps：这个模型还不太好用，需要训练一下，才能写出正确的代码，以上代码经过我部分修正）
其实ITask，是我们定义的一个接口
interface ITask {
fun handleTask(context:Context)
}
我们通过上面方法，就能得到一个通过拓扑算法排序好的List，这个时候我们只需要遍历一遍，调用每个ITask的方法即可
val list = detectCycleNodes()
list.forEach {
it.handleTask(context)
}
总结
我们通过了解一个小算法，就能解决我们的启动时的任务混乱治理的问题
网友评论