简单解释：针对于有向无环图（DAG），给出一个可行的节点排序，使节点之间的依赖关系不冲突。
复杂解释：自行搜索相关资料。
本次应用中的解释：给出一个可行的计算顺序，使得每个字段计算时，所需的变量已经完成了计算。
在开发的报表数据管理系统中，系统的业务流程如下：
① 先从目标数据库中抓取数据值，例如目标系统为物流系统，抓取其中物流订单的相关数据，送货地区、货物体积、数量、型号等数据。
② 对数据进行一定的运算逻辑，如计算总费用= 运费+卸货费
系统在计算的过程中，存在多级计算，如下图中的单价、运费、卸货费、总费用都需要进行计算，如何确定每个字段的计算顺序，保证总费用在计算时，运费已经完成计算了。即系统需要将运费的计算先排在总费用的计算前面。这个时候就可以应用到拓扑排序。
如果系统不去进行这么一个排序的话，用户在添加公式的时候，需要考虑字段之间的顺序是否符合先后顺序， 如果出现了计算总费用时，运费这个字段还没有计算完成的情况，系统会出现报错，用户需要对错误进行排查，导致用户使用体验非常差。
kahn算法说明：
拓扑排序工具类
/**
* @author kstar
* @date 2024/10/16
* @description
* 操作方法见main方法，有详细的操作流程
*/
import java.util.*;
public class GraphUtils {
// 定义点的数据结构
public static class Node {
public Object val;
public int pathIn = 0; // 入链路数量
public Node(Object val) {
this.val = val;
}
}
/**
* 拓扑图类
*/
public static class Graph {
// 图中节点的集合
public Set<Node> vertexSet = new HashSet<Node>();
// 相邻的节点，纪录边
public Map<Node, Set<Node>> adjaNode = new HashMap<Node, Set<Node>>();
// 将节点加入图中
public boolean addNode(Node start, Node end) {
// 判断节点集合中是否有这两个节点，没有的话就加入到节点集合
if (!vertexSet.contains(start)) {
vertexSet.add(start);
}
if (!vertexSet.contains(end)) {
vertexSet.add(end);
}
// 如果图中已经存在该边，则不添加
if (adjaNode.containsKey(start)
&& adjaNode.get(start).contains(end)) {
return false;
}
// 判断当前节点是否有边的map，有的话可以直接加入，没有的话新建一个set
if (adjaNode.containsKey(start)) {
adjaNode.get(start).add(end);
} else {
Set<Node> temp = new HashSet<Node>();
temp.add(end);
adjaNode.put(start, temp);
}
// 被指向的节点入度+1
end.pathIn++;
return true;
}
}
/**Kahn算法
* 0. 维护一个入度为0的队列
* 1. 先找到所有入度为0的点，并从图中移除，加入到入度为0的集合中
* 2. 循环处理setOfZeroIndegree集合中的所有点，
*/
public static class KahnTopo {
private List<Node> result; // 用来存储结果集,结果数据集就是最终的排序结果
private Queue<Node> setOfZeroIndegree; // 用来存储入度为0的顶点
private Graph graph;
//构造函数，初始化
public KahnTopo(Graph di) {
this.graph = di;
this.result = new ArrayList<Node>();
this.setOfZeroIndegree = new LinkedList<Node>();
// 对入度为0的集合进行初始化
for(Node iterator : this.graph.vertexSet){
if(iterator.pathIn == 0){
this.setOfZeroIndegree.add(iterator);
}
}
}
//拓扑排序处理过程
public void process() {
while (!setOfZeroIndegree.isEmpty()) {
Node v = setOfZeroIndegree.poll();
// 将当前顶点添加到结果集中
result.add(v);
if (this.graph.adjaNode.get(v)==null){
this.graph.vertexSet.remove(v);
continue;
}
if(this.graph.adjaNode.keySet().isEmpty()){
return;
}
// 遍历由v引出的所有边
for (Node w : this.graph.adjaNode.get(v) ) {
// 将该边从图中移除，通过减少边的数量来表示
w.pathIn--;
if (0 == w.pathIn) // 如果入度为0，那么加入入度为0的集合
{
setOfZeroIndegree.add(w);
}
}
this.graph.vertexSet.remove(v);
this.graph.adjaNode.remove(v);
}
// 如果此时图中还存在边，那么说明图中含有环路
if (!this.graph.vertexSet.isEmpty()) {
List<String> errNode = new ArrayList<>();
for (Node node : this.graph.vertexSet) {
errNode.add(node.val.toString());
}
throw new IllegalArgumentException("当前参数存在循环依赖，请检查:"+errNode);
}
}
//结果集
public Iterable<Node> getResult() {
return result;
}
}
//测试方法
public static void main(String[] args) {
// 添加点
Node A = new Node("A");
Node B = new Node("B");
Node C = new Node("C");
Node D = new Node("D");
Node E = new Node("E");
Node F = new Node("F");
// 添加边
Graph graph = new Graph();
graph.addNode(A, B);
graph.addNode(B, C);
graph.addNode(B, D);
graph.addNode(D, C);
graph.addNode(E, C);
graph.addNode(C, F);
KahnTopo topo = new KahnTopo(graph);
topo.process();
for(Node temp : topo.getResult()){
System.out.print(temp.val.toString() + "-->");
}
}
}
实际应用代码
// 在实际业务场景中的应用，仅做说明演示，直接复制过去无法使用，要用的话用上面的代码的main方法即可测试
// 样例方法中，需要对CollectSchemeDetail这个类中进行排序，
// 排序时根据类中的getCollectResultCode构建图，将计算时需要的字段解析出来构建图
public void calculateOrder(String collectSchemeCode){
List<CollectSchemeDetail> collectSchemeDetails = listByCode(collectSchemeCode);
Map<String, GraphUtils.Node> nodeMap = new HashMap<>();
// 循环遍历对象数组中的值，取出其中的点和图的关系
for (CollectSchemeDetail schemeDetail : collectSchemeDetails) {
GraphUtils.Node node = new GraphUtils.Node(schemeDetail.getCollectResultCode());
nodeMap.put(schemeDetail.getCollectResultCode(),node);
}
GraphUtils.Graph graph = new GraphUtils.Graph();
for (CollectSchemeDetail schemeDetail : collectSchemeDetails) {
if (schemeDetail.getCollectType().equals(CollectSchemeDetail.CollectTypeEnum.EQUATION)) {
if (schemeDetail.getExpression()==null||!schemeDetail.getExpression().contains("$")){
throw new GlobalException("公式：["+schemeDetail.getCollectResultName()+"]中没有设置表达式，请先设置表达式后再添加");
}
// 公式解析，expression为公式，如A+B-C，
// JEPUtils.getVariables的方法可以将公式中的有效字段解析出来
List<String> variableList = JEPUtils.getVariables(schemeDetail.getExpression());
for (String variable : variableList) {
graph.addNode(nodeMap.get(variable), nodeMap.get(schemeDetail.getCollectResultCode()));
}
}
}
// 执行拓扑排序算法
GraphUtils.KahnTopo topo = new GraphUtils.KahnTopo(graph);
topo.process();
Map<String,List<CollectSchemeDetail>> resultCodeSchemeDetailMap = collectSchemeDetails.stream().collect(Collectors.groupingBy(CollectSchemeDetail::getCollectResultCode));
int i = 1;
List<CollectSchemeDetail> needUpdateList = new ArrayList<>();
// 循环拓扑排序的结果，对数据的计算顺序进行更新
for(GraphUtils.Node temp : topo.getResult()){
for (CollectSchemeDetail collectSchemeDetail : resultCodeSchemeDetailMap.get(temp.val.toString())) {
collectSchemeDetail.setCalculateOrder(i);
}
needUpdateList.addAll(resultCodeSchemeDetailMap.get(temp.val.toString()));
i++;
}
updateBatchById(needUpdateList);
}
处理后字段的计算顺序按照拓扑排序给出的一个可行解进行排序，如在给出的样例图中，运费的计算需要先由地区计算出单价，再由单价*数量得到运费。那么地区、数量、体积的计算顺序应该是0，运费的计算顺序是1，卸货费用的计算顺序是2，总费用的计算顺序为3，总费用= 运费+卸货费用。
至此，用户可以随意的去修改字段之间的计算公式，而不需要考虑计算顺序出现错误。只有在设定的公式存在环路时，系统会返回报错信息，告知用户哪几个字段之间存在环路，让用户重新配置公式。
用户的使用体验得到了优化。
本样例说明源码开源在：
欢迎大家到到项目中多给点star支持，对项目有建议或者有想要了解的欢迎一起讨论