流程图中的回环

回环是指在流程图中根据流程走向形成闭环，如下图：

处理思路

从起始节点开始，遍历所有路径，判断是否回环，直至结束节点。

处理过程

一.数据结构
{"name":"ceshi","nodeList":[{"id":"id1","name":"开始节点","type":"start"},{"id":"id2","name":"结束节点","type":"end"},{"id":"id3","name":"a","type":"task"},{"id":"id4","name":"b","type":"task"},{"id":"id5","name":"c","type":"task"},{"id":"id6","name":"d","type":"task"},{"id":"id7","name":"e","type":"task"}],"lineList":[{"from":"id1","to":"id3"},{"from":"id3","to":"id4"},{"from":"id4","to":"id5"},{"from":"id5","to":"id6"},{"from":"id6","to":"id2"},{"from":"id5","to":"id7"},{"from":"id7","to":"id4"}]}
二.构建数据模型

  
  private FlowDataParser(Map<String, Node> nodeMap){
      this.nodeMap = nodeMap;
  }

  public static FlowDataParser parse(String jsonString){
      FlowContent flowContent = JSONObject.parseObject(jsonString, FlowContent.class);
      List<Map<String, Object>> nodeList = flowContent.nodeList;
      List<Map<String, Object>> lineList = flowContent.lineList;
      Map<String, Node> nodeMap = new HashMap<String, FlowDataParser.Node>();
      // 创建节点
      for (Map<String, Object> map : nodeList) {
          String id = map.get("id").toString();
          Node node = new Node();
          node.content = map;
          node.id = id;
          node.type = map.get("type").toString();
          nodeMap.put(id, node);
      }
      // 创建链表数据结构
      for (Map<String, Object> map : lineList) {
          String fromId = map.get("from").toString();
          String toId = map.get("to").toString();
          Node fromNode = nodeMap.get(fromId);
          Node toNode = nodeMap.get(toId);
          fromNode.nextNodes.add(toNode);
          toNode.preNodes.add(fromNode);
      }
      return new FlowDataParser(nodeMap);
  }
  
  @Data
  private static class FlowContent{
      private String name;
      private List<Map<String, Object>> nodeList;
      private List<Map<String, Object>> lineList;
  }
  
  
  private static class Node {
      // 节点主键
      private String id;
      // 节点类型
      private String type;
      // 上一级节点
      private List<Node> preNodes = new ArrayList<FlowDataParser.Node>();
      // 下一级节点
      private List<Node> nextNodes = new ArrayList<>();
      // 路径节点
      private Set<String> paths = new HashSet<>();
      // 节点内容
      private Map<String, Object> content;
      
  }

三.遍历所有节点校验是否出现回环

    public boolean cycleCheck(){
        List<Node> nodes = new ArrayList<>();
        nodes.add(this.getStartNode());
        // 从开始节点循环遍历，校验回环
        while(true){
            List<Node> nextNodes = new ArrayList<>();
            for (Node n : nodes) {
                if (ifCycle(n)) {
                    // 出现回环
                    return false;
                } else if (CollectionUtils.isNotEmpty(n.nextNodes)) {
                    // 没有出现回环，获取下级节点，继续遍历
                    nextNodes.addAll(n.nextNodes);
                }
            }
            
            if (nextNodes.size() == 0) {
                // 不存在下级节点，流程结束
                return true;
            } else {
                // 继续遍历
                nodes = nextNodes;
            }
        }
    }
    
    // 查找开始节点
    private Node getStartNode(){
        for(Map.Entry<String, Node> entry : this.nodeMap.entrySet()){
            if ("start".equals(entry.getValue().type)) {
                return entry.getValue();
            }
        }
        return null;
    }
    
    
    private boolean ifCycle(Node node){
        Set<String> paths = node.paths;
        List<Node> nextNodes = node.nextNodes;
        
        if (CollectionUtils.isNotEmpty(nextNodes)) {
            for (Node nextNode : nextNodes) {
                if (paths.contains(nextNode.id)
                        || node.id.equals(nextNode.id)) {
                    // 路径节点中包含下一个节点，出现回环
                    return true;
                } else {
                    // 路径节点中不包含下一级节点，没有出现回环，下级节点收集路径信息
                    nextNode.paths.addAll(node.paths);
                    nextNode.paths.add(node.id);
                }
            }
        }
        return false;
    }

四.跑一下代码，看下结果

        String flowDataStr = "{    \"name\":\"ceshi\",    \"nodeList\":[        {            \"id\":\"id1\",\"name\":\"开始节点\",\"type\":\"start\"        },        {            \"id\":\"id2\",\"name\":\"结束节点\",\"type\":\"end\"        },        {            \"id\":\"id3\",\"name\":\"a\",\"type\":\"task\"        },        {            \"id\":\"id4\",\"name\":\"b\",\"type\":\"task\"        },        {            \"id\":\"id5\",\"name\":\"c\",\"type\":\"task\"        },        {            \"id\":\"id6\",\"name\":\"d\",\"type\":\"task\"        },        {            \"id\":\"id7\",\"name\":\"e\",\"type\":\"task\"        }    ],    \"lineList\":[        {\"from\":\"id1\",\"to\":\"id3\"},        {\"from\":\"id3\",\"to\":\"id4\"},        {\"from\":\"id4\",\"to\":\"id5\"},        {\"from\":\"id5\",\"to\":\"id6\"},        {\"from\":\"id6\",\"to\":\"id2\"},                {\"from\":\"id5\",\"to\":\"id7\"},        {\"from\":\"id7\",\"to\":\"id4\"}    ]}";
        FlowDataParser parser = FlowDataParser.parse(flowDataStr);
        if (parser.cycleCheck()) {
            System.out.println("校验成功");
        } else {
            System.out.println("校验失败,出现回环");
        }
    }

在写遍历的时候原本使用了递归，结果递归次数太多stackoverflow了，改成了循环，小计一下