多叉树+图实现简单业务流程

场景

     这次遇到一个需求,大致就是任务组织成方案,方案组织成预案,预案可裁剪调整.预案关联事件等级配置,告警触发预案产生事件.然后任务执行是有先后的,也就是有流程概念.

整体架构流程

     方案管理、预案管理构成任务流程的基础条件,告警信息关联预案配置构成事件,也就是流程启动的入口信息.

业务界面

技术细节

     其实也没有什么特殊的技术,也就用到了多叉树、图、最长路径计算(深搜)等.

• 多叉树

import lombok.Data;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zwmac
 */
@Data
public class MoreParentTreeNode<T> {
    /**
     * 节点的唯一标识符
     */
    private Long id;
    /**
     * 节点的名称
     */
    private String name;
    /**
     * 节点的索引
     */
    private Integer index;
    /**
     * 子节点list
     */
    private List<MoreParentTreeNode<T>> children;
    /**
     * 父节点list
     */
    private List<MoreParentTreeNode<T>> parents;

    /**
     * 扩展信息(一般就存节点对应的原始数据)
     */
    private T extendInfo;

    public MoreParentTreeNode(Long id, String name,Integer index) {
        this.id = id;
        this.name = name;
        this.index = index;
        this.children = new ArrayList<>();
        this.parents = new ArrayList<>();
    }

    public MoreParentTreeNode() {

    }

    /**
     * 添加子节点
     * @param child 子节点
     */
    public void addChild(MoreParentTreeNode<T> child) {
        if (this.children.contains(child)) {
            return;
        }
        this.children.add(child);
        child.parents.add(this);
    }

    /**
     * 添加父节点
     * @param parent 父节点
     */
    public void addParent(MoreParentTreeNode<T> parent) {
        if (this.parents.contains(parent)) {
            return;
        }
        this.parents.add(parent);
        parent.children.add(this);
    }

    public void traverse() {
        System.out.println(this.name); // 打印节点名称

        if (this.children.isEmpty()) {
            System.out.println("没有子节点");
        }

        for (MoreParentTreeNode<T> child : this.children) {
            child.traverse(); // 递归遍历子节点
        }
    }

    public static void main(String[] args) {
        MoreParentTreeNode root = new MoreParentTreeNode(1L, "root",1);
        MoreParentTreeNode node1 = new MoreParentTreeNode(2L, "node1",2);
        MoreParentTreeNode node2 = new MoreParentTreeNode(3L, "node2",3);
        MoreParentTreeNode node3 = new MoreParentTreeNode(4L, "node3",4);
        MoreParentTreeNode node4 = new MoreParentTreeNode(5L, "node4",5);
        MoreParentTreeNode node5 = new MoreParentTreeNode(5L, "node5",6);
        MoreParentTreeNode node6 = new MoreParentTreeNode(6L, "node6",7);


        root.addChild(node1);
        root.addChild(node2);
        node1.addChild(node6);
        node3.addParent(node2);
        node4.addParent(node2);
        node4.addParent(node1);
        node5.addParent(node4);

        root.traverse();
    }
}

• 图对象与计算基本方法

import lombok.Data;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 流程图对象,用于计算最长执行时间
 * @author zwmac
 */
@Data
public class ProcessGraph {
    /**
     * 顶点个数
     */
    private int numVertices;
    /**
     * 邻接表
     */
    private List<List<Integer>> adjList;
    /**
     * 顶点执行时间(边长)
     */
    private Double[] executionTimes;

    /**
     * 构造函数
     * @param numVertices 顶点个数
     * @param executionTimes 顶点执行时间(边长)
     */
    public ProcessGraph(int numVertices, Double[] executionTimes) {
        this.numVertices = numVertices;
        this.executionTimes = executionTimes;
        adjList = new ArrayList<>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    /**
     * 添加边
     * @param src 源顶点
     * @param dest 目标顶点
     */
    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
    }

    /**
     * 计算最长执行时间
     * @return 最长执行时间
     */
    public Double findMaxExecutionTime() {
        Double[] maxExecutionTimes = new Double[numVertices];
        Arrays.fill(maxExecutionTimes, -1d);

        Double maxExecutionTime = 0d;

        for (int i = 0; i < numVertices; i++) {
            Double currentExecutionTime = dfs(i, maxExecutionTimes);
            if (currentExecutionTime > maxExecutionTime) {
                maxExecutionTime = currentExecutionTime;
            }
        }

        return maxExecutionTime;
    }

    /**
     * 深度优先搜索
     * @param vertex 顶点
     * @param maxExecutionTimes 最长执行时间数组
     * @return 最长执行时间
     */
    private Double dfs(int vertex, Double[] maxExecutionTimes) {
        if (maxExecutionTimes[vertex] != -1) {
            return maxExecutionTimes[vertex];
        }

        Double maxExecutionTime = executionTimes[vertex];

        for (int neighbor : adjList.get(vertex)) {
            Double neighborExecutionTime = dfs(neighbor, maxExecutionTimes);
            if (neighborExecutionTime + executionTimes[vertex] > maxExecutionTime) {
                maxExecutionTime = neighborExecutionTime + executionTimes[vertex];
            }
        }

        maxExecutionTimes[vertex] = maxExecutionTime;
        return maxExecutionTime;
    }

    public static void main(String[] args) {
        Double[] executionTimes = {0d,3d, 4d, 5d, 2d, 3d,0d};

        ProcessGraph graph = new ProcessGraph(7, executionTimes);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 5);
        graph.addEdge(3, 5);
        //graph.addEdge(3, 5);

        Double maxExecutionTime = graph.findMaxExecutionTime();
        System.out.println("Max execution time: " + maxExecutionTime);
    }
}

• 多叉树工具类

import cn.hutool.core.bean.BeanUtil;
import cn.hutool.core.collection.CollectionUtil;
import cn.hutool.core.util.ArrayUtil;
import cn.hutool.core.util.RandomUtil;
import cn.hutool.json.JSONUtil;
import com.smartPark.business.emergency.event.entity.EmergencyEventTask;
import com.smartPark.business.emergency.event.entity.dto.EmergencyEventTaskDTO;
import org.apache.commons.lang3.StringUtils;

import java.util.*;

/**
 * @author zwmac
 */
public class EventTaskTreeUtil {
    /**
     * 转换流程树
     * @param eventTaskList 任务列表
     * @return 流程树根节点
     */
    public static MoreParentTreeNode<?> convertTreeDto(List<EmergencyEventTaskDTO> eventTaskList) {
        MoreParentTreeNode<?> root = new MoreParentTreeNode<>(0L,"开始",0);
        EmergencyEventTaskDTO rootEventTaskDto = new EmergencyEventTaskDTO();
        rootEventTaskDto.setTaskDuration(0d);

        Map<Long, MoreParentTreeNode<?>> nodeMap = new HashMap<>();
        for (int i = 0;i < eventTaskList.size();i++) {
            EmergencyEventTaskDTO eventTask = eventTaskList.get(i);
            Long id = eventTask.getId();
            String name = eventTask.getTaskName();
            MoreParentTreeNode<EmergencyEventTaskDTO> node = new MoreParentTreeNode<>(id,name,(i+1));
            node.setExtendInfo(eventTask);
            nodeMap.put(eventTask.getId(), node);
        }

        //处理父子关系(正)
        for (EmergencyEventTaskDTO eventTask : eventTaskList) {
            transNodeRef(eventTask, nodeMap, root);
        }

        //处理父子关系(反)
        for (int i = eventTaskList.size() - 1;i > -1; i--){
            EmergencyEventTaskDTO eventTask = eventTaskList.get(i);

            transNodeRef(eventTask, nodeMap, root);
        }


        return root;
    }

    /**
     * 转换流程树
     * @param eventTaskList 任务列表
     * @return 流程树根节点
     */
    public static MoreParentTreeNode<?> convertTree(List<EmergencyEventTask> eventTaskList) {
        MoreParentTreeNode<?> root = new MoreParentTreeNode<>(0L,"开始",0);
        EmergencyEventTask rootEventTask = new EmergencyEventTask();
        rootEventTask.setTaskDuration(0d);

        Map<Long, MoreParentTreeNode<?>> nodeMap = new HashMap<>();
        for (int i = 0;i < eventTaskList.size();i++) {
            EmergencyEventTask eventTask = eventTaskList.get(i);
            Long id = eventTask.getId();
            String name = eventTask.getTaskName();
            MoreParentTreeNode<EmergencyEventTask> node = new MoreParentTreeNode<>(id,name,(i+1));
            node.setExtendInfo(eventTask);
            nodeMap.put(eventTask.getId(), node);
        }

        //处理父子关系(正)
        for (EmergencyEventTask eventTask : eventTaskList) {
            EmergencyEventTaskDTO eventTaskDTO = new EmergencyEventTaskDTO();
            BeanUtil.copyProperties(eventTask, eventTaskDTO);
            transNodeRef(eventTaskDTO, nodeMap, root);

        }

        //处理父子关系(反)
        for (int i = eventTaskList.size() - 1;i > -1; i--){
            EmergencyEventTask eventTask = eventTaskList.get(i);
            EmergencyEventTaskDTO eventTaskDTO = new EmergencyEventTaskDTO();
            BeanUtil.copyProperties(eventTask,eventTaskDTO);
            transNodeRef(eventTaskDTO, nodeMap, root);
        }


        return root;
    }

    /**
     * 转换节点关系
     * @param eventTask 父级任务
     * @param nodeMap 节点map
     * @param root 根节点
     */
    private static void transNodeRef(EmergencyEventTaskDTO eventTask, Map<Long, MoreParentTreeNode<?>> nodeMap, MoreParentTreeNode<?> root) {
        Long id = eventTask.getId();
        MoreParentTreeNode<?> node = nodeMap.get(id);
        if (node != null){
            EmergencyEventTaskDTO eventTaskDTO = new EmergencyEventTaskDTO();
            Object eventTaskObj = node.getExtendInfo();
            if(eventTaskObj instanceof EmergencyEventTask) {
                EmergencyEventTask nodeEventTask = (EmergencyEventTask) eventTaskObj;
                BeanUtil.copyProperties(nodeEventTask, eventTaskDTO);
            }
            String preIds = eventTaskDTO.getBeforeTaskIds();
            if (StringUtils.isEmpty(preIds)){
                node.addParent(root);
                root.addChild(node);
            }else {
                String[] preIdsArr = preIds.split(",");
                if (ArrayUtil.isNotEmpty(preIdsArr)){
                    for (String preId : preIdsArr) {
                        MoreParentTreeNode<?> preNode = nodeMap.get(Long.valueOf(preId));
                        //前置任务不为空
                        if (preNode != null){
                            preNode.addChild(node);
                        }
                    }
                }
            }
            nodeMap.put(id, node);

        }
    }

    /**
     * 获取节点的子节点列表
     * @param treeNode 节点
     * @param eventTaskId 事件任务id
     * @return 子节点列表
     */
    public static List<? extends MoreParentTreeNode<?>> getNodeChildrenList(MoreParentTreeNode<?> treeNode, Long eventTaskId) {

        List<? extends MoreParentTreeNode<?>> childrenList = itGetNodeChildrenList(treeNode, eventTaskId);
        if (CollectionUtil.isNotEmpty(childrenList)) {
            return childrenList;
        }
        childrenList = itGetNodeParentList(treeNode, eventTaskId);
        return childrenList;
    }

    /**
     * 迭代获取节点的父节点列表
     * @param moreParentTreeNode 父节点
     * @param eventTaskId 事件任务id
     * @return 父节点列表
     */
    private static List<? extends MoreParentTreeNode<?>> itGetNodeParentList(MoreParentTreeNode<?> moreParentTreeNode, Long eventTaskId) {
        List<? extends MoreParentTreeNode<?>> children = null;
        if (moreParentTreeNode.getId().equals(eventTaskId)){
            children = moreParentTreeNode.getChildren();
        }else{
            List<? extends MoreParentTreeNode<?>> parentTreeNodes = moreParentTreeNode.getParents();
            if(CollectionUtil.isNotEmpty(parentTreeNodes)) {
                for (MoreParentTreeNode<?> parentTreeNode : parentTreeNodes) {
                    children = itGetNodeParentList(parentTreeNode, eventTaskId);
                    if (CollectionUtil.isNotEmpty(children)) {
                        break;
                    }
                }
            }
        }
        return children;
    }

    /**
     * 迭代获取节点的子节点列表
     * @param moreParentTreeNode 子节点
     * @param eventTaskId 事件任务id
     * @return 子节点列表
     */
    private static List<? extends MoreParentTreeNode<?>> itGetNodeChildrenList(MoreParentTreeNode<?> moreParentTreeNode, Long eventTaskId) {
        List<? extends MoreParentTreeNode<?>> children = null;
        if (moreParentTreeNode.getId().equals(eventTaskId)){
            children = moreParentTreeNode.getChildren();
        }else{
            List<? extends MoreParentTreeNode<?>> childrenChild = moreParentTreeNode.getChildren();
            if(CollectionUtil.isNotEmpty(childrenChild)) {
                for (MoreParentTreeNode<?> parentTreeNode : childrenChild) {
                    children = itGetNodeChildrenList(parentTreeNode, eventTaskId);
                    if (CollectionUtil.isNotEmpty(children)) {
                        break;
                    }
                }
            }
        }
        return children;

    }

    public static void main(String[] args) {
        List<EmergencyEventTaskDTO> eventTaskList = new ArrayList<>();
        initTestData(eventTaskList,9);
        System.out.println(JSONUtil.toJsonStr(eventTaskList));

        MoreParentTreeNode<?> treeNode = convertTreeDto(eventTaskList);

        List<?> childrenList = getNodeChildrenList(treeNode, 3L);

        treeNode.traverse();

    }

    private static void initTestData(List<EmergencyEventTaskDTO> eventTaskList, int num) {
        for (int i = 0;i < num; i++){
            EmergencyEventTaskDTO eventTask = new EmergencyEventTaskDTO();
            eventTask.setId(Long.valueOf(i));
            eventTask.setTaskName("任务-" + (i + 1));
            eventTask.setTaskDuration(RandomUtil.randomDouble(1,10));
            if (i > 1){
                StringJoiner sj = new StringJoiner(",");
                int n = RandomUtil.randomInt(0,i);
                for(int j = 0;j < i - 1 - n;j++){
                    sj.add(String.valueOf(j+1));
                }
                eventTask.setBeforeTaskIds(sj.toString());
            }
            eventTaskList.add(eventTask);
        }
    }


}

     使用思路也特别简单,实际就是将配置任务时只选择了节点上级任务的所有任务构成一个多叉树,然后跟这个树每个节点设置唯一编号,然后转化为图,计算最长路径作为事件的预计完成时间,最后就是各个任务节点的流转了.

/**
     * 计算预计完成时间
     * @param event 事件
     * @return 预计完成时间
     */
    private Date calPlanEndTime(EmergencyEvent event) {
        Date planStartTime = event.getPlanStartTime();
        Date finalNow = planStartTime;
        //先查询预案任务
        QueryWrapper<EmergencyEventPlan> eventPlanQw = new QueryWrapper<>();
        eventPlanQw.eq("event_id_", event.getId());
        List<EmergencyEventPlan> eventPlanList = eventPlanService.list(eventPlanQw);
        if (CollectionUtil.isNotEmpty(eventPlanList)){
            //最终预计完成时间
            //再查询预案任务
            for (int i = 0;i < eventPlanList.size();i++){
                QueryWrapper<EmergencyEventTask> eventTaskQw = new QueryWrapper<>();
                eventTaskQw.eq("event_id_", event.getId());
                eventTaskQw.eq("event_plan_id_", eventPlanList.get(i).getId());
                List<EmergencyEventTask> eventTaskList = eventPlanTaskService.list(eventTaskQw);
                if (CollectionUtil.isNotEmpty(eventTaskList)){

                    //再组织流程树
                    MoreParentTreeNode<?> processTree = EventTaskTreeUtil.convertTree(eventTaskList);

                    //最后计算时间
                    Date planTaskEndTime = calEndTime(processTree, planStartTime, eventTaskList);
                    if (planTaskEndTime.after(finalNow)){
                        finalNow = planTaskEndTime;
                    }
                }

            }

        }

        return finalNow;
    }

小结

• 后悔数据结构没有学好
• 算法用的少,也有很大工具包直接提供,但是还是很有学的必要的
       就随便写写,希望能帮到大家,uping!