上海培训网站建设,媒体网站的销售怎么做,怎么登录住建局官网,在线教育网站设计1. 拓扑排序说明
简单解释#xff1a;针对于有向无环图#xff08;DAG#xff09;#xff0c;给出一个可行的节点排序#xff0c;使节点之间的依赖关系不冲突。
复杂解释#xff1a;自行搜索相关资料。
本次应用中的解释#xff1a;给出一个可行的计算顺序#xff0…1. 拓扑排序说明
简单解释针对于有向无环图DAG给出一个可行的节点排序使节点之间的依赖关系不冲突。
复杂解释自行搜索相关资料。
本次应用中的解释给出一个可行的计算顺序使得每个字段计算时所需的变量已经完成了计算。
2. 业务场景
在开发的报表数据管理系统中系统的业务流程如下
① 先从目标数据库中抓取数据值例如目标系统为物流系统抓取其中物流订单的相关数据送货地区、货物体积、数量、型号等数据。
② 对数据进行一定的运算逻辑如计算总费用 运费卸货费
问题难点
系统在计算的过程中存在多级计算如下图中的单价、运费、卸货费、总费用都需要进行计算如何确定每个字段的计算顺序保证总费用在计算时运费已经完成计算了。即系统需要将运费的计算先排在总费用的计算前面。这个时候就可以应用到拓扑排序。
如果系统不去进行这么一个排序的话用户在添加公式的时候需要考虑字段之间的顺序是否符合先后顺序 如果出现了计算总费用时运费这个字段还没有计算完成的情况系统会出现报错用户需要对错误进行排查导致用户使用体验非常差。 3. 实际应用代码
kahn算法说明
维护一个入度为0的队列先找到所有入度为0的点并从图中移除加入到入度为0的队列中即setOfZeroIndegree循环处理setOfZeroIndegree队列中的所有点将点向外指出的边进行删除A-BA的入度为0 B的入度为1删除掉A点和B点的边后B点的入度为0这个时候B点也可以加入setOfZeroIndegree队列中挡setOfZeroIndegree队列为空时判断图中是否还有边没有删除干净如果没有删除干净则当前图为有环图无法得到可行解。如果删除干净了表示给出的图是有可行解的。
拓扑排序工具类
/*** 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 SetNode vertexSet new HashSetNode();// 相邻的节点纪录边public MapNode, SetNode adjaNode new HashMapNode, SetNode();// 将节点加入图中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有的话可以直接加入没有的话新建一个setif (adjaNode.containsKey(start)) {adjaNode.get(start).add(end);} else {SetNode temp new HashSetNode();temp.add(end);adjaNode.put(start, temp);}// 被指向的节点入度1end.pathIn;return true;}}/**Kahn算法* 0. 维护一个入度为0的队列* 1. 先找到所有入度为0的点并从图中移除加入到入度为0的集合中* 2. 循环处理setOfZeroIndegree集合中的所有点*/public static class KahnTopo {private ListNode result; // 用来存储结果集,结果数据集就是最终的排序结果private QueueNode setOfZeroIndegree; // 用来存储入度为0的顶点private Graph graph;//构造函数初始化public KahnTopo(Graph di) {this.graph di;this.result new ArrayListNode();this.setOfZeroIndegree new LinkedListNode();// 对入度为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()) {ListString errNode new ArrayList();for (Node node : this.graph.vertexSet) {errNode.add(node.val.toString());}throw new IllegalArgumentException(当前参数存在循环依赖请检查:errNode);}}//结果集public IterableNode 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){ListCollectSchemeDetail collectSchemeDetails listByCode(collectSchemeCode);MapString, 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为公式如AB-C// JEPUtils.getVariables的方法可以将公式中的有效字段解析出来ListString 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();MapString,ListCollectSchemeDetail resultCodeSchemeDetailMap collectSchemeDetails.stream().collect(Collectors.groupingBy(CollectSchemeDetail::getCollectResultCode));int i 1;ListCollectSchemeDetail 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);}4. 解决问题
处理后字段的计算顺序按照拓扑排序给出的一个可行解进行排序如在给出的样例图中运费的计算需要先由地区计算出单价再由单价*数量得到运费。那么地区、数量、体积的计算顺序应该是0运费的计算顺序是1卸货费用的计算顺序是2总费用的计算顺序为3总费用 运费卸货费用。
至此用户可以随意的去修改字段之间的计算公式而不需要考虑计算顺序出现错误。只有在设定的公式存在环路时系统会返回报错信息告知用户哪几个字段之间存在环路让用户重新配置公式。
用户的使用体验得到了优化。
5. 相关链接
本样例说明源码开源在 ruoyi-reoprt gitee仓库 ruoyi-report github仓库 欢迎大家到到项目中多给点star支持对项目有建议或者有想要了解的欢迎一起讨论
