流程图中的回环
回环是指在流程图中根据流程走向形成闭环,如下图:
处理思路
从起始节点开始,遍历所有路径,判断是否回环,直至结束节点。
处理过程
一.数据结构
{"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了,改成了循环,小计一下