有向无环图的java实现(使用矩阵特性开发)

工作流如下图所示,要求每一个任务只执行一次,不重复执行,要求任务的所有前置任务必须完成才能往后执行,例如任务7必须在任务13,2,3三个任务完成之后才能执行,而任务13,2,3属于独立的任务,可以并发执行

 

根据多线程求得出6个路线数据

每个线程可以独立执行,所有线程相同的任务不能重复执行,当前任务必须在前置任务完成之后才能执行,

路线:[1, 2, 7, 10, 12] 路线:[1, 13, 7, 10, 12] 路线:[1, 3, 7, 10, 12] 路线:[1, 4, 8, 10, 12] 路线:[1, 4, 9, 11, 12] 路线:[1, 5, 6, 9, 11, 12]

路线不能出现回环,出现即死循环,需要提前排除

 

 

实现代码如下(JDK1.8)

数据结构类NetWork

import java.util.*; /** * 图解网络数据结构 */ public class NetWork { //记录两份网络节点,使用空间换时间,提升反向查询效率 //网络初始化,x_k,y_k private Map<String, Map<String, String>> xMapMap; //网络初始化,y_k,x_k private Map<String, Map<String, String>> yMapMap; //回环路径 private List<String> loopbackList;//回环地址 //节点深度路径 private List<List<String>> deepPathList;//深度路径 private Map<String, String> jobMapStatus;//map任务状态 enum TYPE {X,Y} public NetWork() { xMapMap = new HashMap();//X点集 yMapMap = new HashMap();//Y点集 loopbackList = new LinkedList<>();//回环地址 deepPathList = new LinkedList<>();//深度路径 } /** * 初始化任务 */ public void initJob() { jobMapStatus = new HashMap<>(); Set<String> allPoint = getAllPoint(); allPoint.forEach(job -> jobMapStatus.put(job, "0"));//0,1 0表示未执行,1表示执行 } /** * 获取任务的转状态 * * @param job * @return */ public String getJobMapStatus(String job) { String status = jobMapStatus.get(job); return status; } /** * 更新任务的状态 * * @param job 任务名称 * @param status 任务状态 */ public void setJobMapStatus(String job, String status) { jobMapStatus.put(job, status); } public List<String> getLoopbackList() { return loopbackList; } public List<List<String>> getDeepPathList() { return deepPathList; } /** * 网络添加节点 * * @param xPoint x位 * @param yPoint y位 * @param distance 位移 */ public void addPoint(String xPoint, String yPoint, String distance) { if (!xMapMap.containsKey(xPoint)) {//记录x的索引 xMapMap.put(xPoint, new HashMap<>()); } xMapMap.get(xPoint).put(yPoint, distance); if (!yMapMap.containsKey(yPoint)) {//记录y的索引 yMapMap.put(yPoint, new HashMap<>()); } yMapMap.get(yPoint).put(xPoint, distance); } /** * 根据坐标获取某点 * * @param xPoint * @param yPoint * @return */ public String getPoint(String xPoint, String yPoint) { Map<String, String> linePoints = xMapMap.get(xPoint); String point = linePoints.get(yPoint); return point; } public String getPoint(String point1, String point2, TYPE type) { if (type == TYPE.X) { Map<String, String> linePoints = xMapMap.get(point1); String point = linePoints.get(point2); return point; } else { Map<String, String> linePoints = yMapMap.get(point1); String point = linePoints.get(point2); return point; } } /** * 获取X轴的一列数据 * * @param xPoint * @return */ public List<Map<String, String>> getLinePoint(String xPoint) { List<Map<String, String>> linePointList = new ArrayList<Map<String, String>>(); Map<String, String> linePoints = xMapMap.get(xPoint); if (linePoints != null) { for (Map.Entry<String, String> pointUnit : linePoints.entrySet()) { Map<String, String> pointMap = new HashMap<String, String>(); pointMap.put("X", xPoint); pointMap.put("Y", pointUnit.getKey()); pointMap.put("D", pointUnit.getValue()); linePointList.add(pointMap); } } return linePointList; } /** * 根据类型获取某轴的一列数据 * * @param point 索引点 * @param type 类型 * @return */ public List<Map<String, String>> getLinePoint(String point, TYPE type) { List<Map<String, String>> linePointList = new ArrayList<Map<String, String>>(); if (type == TYPE.X) { Map<String, String> linePoints = xMapMap.get(point); if (linePoints != null) { for (Map.Entry<String, String> pointUnit : linePoints.entrySet()) { Map<String, String> pointMap = new HashMap<String, String>(); pointMap.put("X", point); pointMap.put("Y", pointUnit.getKey()); pointMap.put("D", pointUnit.getValue()); linePointList.add(pointMap); } } } else { Map<String, String> linePoints = yMapMap.get(point); if (linePoints != null) { for (Map.Entry<String, String> pointUnit : linePoints.entrySet()) { Map<String, String> pointMap = new HashMap<String, String>(); pointMap.put("X", pointUnit.getKey()); pointMap.put("Y", point); pointMap.put("D", pointUnit.getValue()); linePointList.add(pointMap); } } } return linePointList; } /** * @param netWork 网络节点 * @param startPoint 起始节点 * @param pathList 当前任务的路径 */ public void recursive(NetWork netWork, String startPoint, ArrayList<String> pathList) { if (pathList.contains(startPoint)) {netWork.getLoopbackList().add(pathList.toString() + "->" + startPoint);return;} pathList.add(startPoint); List<Map<String, String>> linePoint = netWork.getLinePoint(startPoint, NetWork.TYPE.X); if (linePoint.size() == 0) { ArrayList<String> descList = new ArrayList<>(pathList.size()); pathList.forEach(path -> descList.add(path)); netWork.getDeepPathList().add(descList); } for (Map<String, String> map : linePoint) {recursive(netWork, map.get("Y"), pathList);} pathList.remove(startPoint); } /** * 获取所有的点,合并key * * @return */ public Set<String> getAllPoint() { Set<String> allSet1 = xMapMap.keySet(); Set<String> allSet2 = yMapMap.keySet(); Set<String> allSet = new HashSet<>(); allSet.addAll(allSet1); allSet.addAll(allSet2); return allSet; } /** * 显示路径 */ public void show() { int placeholder = 3; String placeholderSrting = ""; for (int i = 0; i < placeholder; i++) {placeholderSrting = placeholderSrting + "-";} Set<String> allSet = getAllPoint();//获取所有的点,用于遍历 System.out.print(String.format("%-" + placeholder + "s", "")); System.out.print(" "); for (String x : allSet) { System.out.print(String.format("%-" + placeholder + "s", x)); } System.out.println(); System.out.print(String.format("%-" + placeholder + "s", "X\\Y")); System.out.print(" "); for (String ignored : allSet) {System.out.print(placeholderSrting);} System.out.println(); for (String x : allSet) { System.out.print(String.format("%-" + placeholder + "s|", x)); for (String y : allSet) { Map<String, String> linePoints = xMapMap.get(x); String point = "0"; if (linePoints != null && linePoints.get(y) != null) { point = linePoints.get(y); } System.out.print(String.format("%-" + placeholder + "s", point)); } System.out.println(); } } }

 

测试类TestMain

import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentMap; /** * 网络计算 */ public class TestMain { public static ConcurrentMap<String, List<String>> println = new ConcurrentHashMap<>(); public static List<String> strings = new ArrayList<>(); public static void main(String[] args) throws InterruptedException { NetWork netWork = new NetWork(); netWork.addPoint("1", "2", "1"); netWork.addPoint("1", "3", "1"); netWork.addPoint("1", "4", "1"); netWork.addPoint("1", "5", "1"); netWork.addPoint("1", "13", "1"); netWork.addPoint("2", "7", "1"); netWork.addPoint("3", "7", "1"); netWork.addPoint("13", "7", "1"); netWork.addPoint("4", "8", "1"); netWork.addPoint("4", "9", "1"); netWork.addPoint("5", "6", "1"); netWork.addPoint("6", "9", "1"); netWork.addPoint("7", "10", "1"); netWork.addPoint("8", "10", "1"); netWork.addPoint("9", "11", "1"); netWork.addPoint("10", "12", "1"); netWork.addPoint("11", "12", "1"); netWork.initJob();//初始化所有节点任务 //netWork.addPoint("6", "1", "1");netWork.addPoint("4", "6", "1");//回环的两条数据 netWork.show(); //获取起点,如图起点为1 String startPoint = "1"; netWork.recursive(netWork, startPoint, new ArrayList<>()); //递归计算所有节点的路径 if (netWork.getLoopbackList().size() != 0) { System.out.println("出现回环地址,回环地址的路径为:" + netWork.getLoopbackList()); return; } //开始计算任务 for (List<String> pathJobList : netWork.getDeepPathList()) { new Thread(() -> { System.out.println("路线:" + pathJobList); for (int i = 0; i < pathJobList.size(); i++) { String job = pathJobList.get(i); List<String> linePoint = new ArrayList<>();//获取任务前置条件 netWork.getLinePoint(job, NetWork.TYPE.Y).forEach(jobLine -> linePoint.add(jobLine.get("X"))); /*System.out.println("任务" + job + "的前置条件:" + linePoint);*/ execJob(job, linePoint, netWork);//执行任务 } }).start(); } Thread.sleep(1000);//这里使用的休眠进行下一次判断,也可以使用锁同步数据,使用锁实现较为复杂 for (Map.Entry<String, List<String>> entry : println.entrySet()) { System.out.println(entry); } System.out.println("执行顺序:" + strings); } /** * 执行任务 * * @param job */ private static void execJob(String job, List<String> linePoint, NetWork netWork) { List<String> tmp = new ArrayList<>(); while (true) { for (String precondition : linePoint) { String jobMapStatus; synchronized (String.class) {jobMapStatus = netWork.getJobMapStatus(precondition);} if (!"1".equals(jobMapStatus)) {tmp.add(precondition);}//未执行 } if (tmp.size() == 0) {break;} linePoint.clear(); tmp.forEach(jobTmp -> linePoint.add(jobTmp)); tmp.clear(); /*此处可以随机数休眠模拟任务执行所需的时间*/ } String jobMapStatus; Boolean status = false;//是否需要执行任务 synchronized (String.class) { jobMapStatus = netWork.getJobMapStatus(job); if ("1".equals(jobMapStatus)) {return;}//任务已经完成 if ("0".equals(jobMapStatus)) {netWork.setJobMapStatus(job, "-1");status = true;}//立即执行 } if (status) { synchronized (String.class) { if (!println.containsKey(Thread.currentThread().getName())) { println.put(Thread.currentThread().getName(), new ArrayList<>()); } println.get(Thread.currentThread().getName()).add(job);strings.add(job); netWork.setJobMapStatus(job, "1"); } } } }

测试结果如下

 

 

实现原理是使用矩阵,X轴表示起始点,Y轴表示结束点,起始点与结束点对应的值为1 即表示起始点与结束点之间是一条通线,如果值为0 即表示这两点之间不通

根据矩阵原理开发

    起始点对应的一行中所有值为1的结束点为起始点可到达的结束点

    结束点对应的一列中所有值为1的起始点是结束点所表示任务的前置任务

 

所以数据结构NetWork类中已经封装好了通过x,y坐标获取一个值和通过x或者通过y获取一行或者一列数据的方法