有向无环图的java实现(使用矩阵特性开发)
工作流如下图所示,要求每一个任务只执行一次,不重复执行,要求任务的所有前置任务必须完成才能往后执行,例如任务7必须在任务13,2,3三个任务完成之后才能执行,而任务13,2,3属于独立的任务,可以并发执行
根据多线程要求得出5个路线数据
每个线程可以独立执行,所有线程相同的任务不能重复执行,当前任务必须在前置任务完成之后才能执行,
路线:[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();
// try {Thread.sleep(100);} catch (InterruptedException e) { e.printStackTrace();}
}
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获取一行或者一列数据的方法