判断是否存在循环引用

有向图的拓扑排序算法，可以增加计数，防止一直递归下去。

/**
 * 检查变量是否满足无循环引用的条件
 *
 * @param variables 变量
 * @return 检查结果是否成功
 */
public boolean checkVariableCycle(List<VariableInfo> variables) {
    if (CollectionUtils.isEmpty(variables)) {
        return true;
    }
    // 构造引用关系
    List<Pair<String, String>> varRelations = genVarRelation(variables);
    List<String> varIds =
        variables.stream().map(variableInfo -> String.valueOf(variableInfo.getId())).collect(Collectors.toList());
    return !hasCycle(varIds, varRelations);
}
/**
 * 0->1
 * 1->2
 * 2->3
 * 3->0
 */
private List<Pair<String, String>> genVarRelation(List<VariableInfo> variableInfoList) {
    List<Pair<String, String>> varRelations = new ArrayList<Pair<String, String>>();
    for (VariableInfo variableInfo : variableInfoList) {
        String varSource = String.valueOf(variableInfo.getId());
        //getVars函数获取该变量引用了哪些其他变量（存在变量的parameter中）。
        List<String> vars = StringUtil.getVars(variableInfo.getParameter());
        for (String varTarget : vars) {
            varRelations.add(Pair.of(varSource, varTarget));
        }
    }
    return varRelations;
}

private boolean hasCycle(List<String> variables, List<Pair<String, String>> varRelations) {
    Map<String, Integer> indegree = new HashMap<String, Integer>();
    for (Pair<String, String> varPair : varRelations) {
        String targetVar = varPair.getRight();
        indegree.put(targetVar, (indegree.get(targetVar) == null ? 0 : indegree.get(targetVar)) + 1);
    }
    // 入度为0的变量入队列
    Queue<String> queue = new LinkedList<String>();
    for (String variable : variables) {
        if (!indegree.containsKey(variable) || indegree.get(variable) == 0) {
            queue.offer(variable);
        }
    }
    while (!queue.isEmpty()) {
        String curVar = queue.poll();
        for (Pair<String, String> varPair : varRelations) {
            String sourceVar = varPair.getLeft();
            String targetVar = varPair.getRight();
            if (curVar.equals(sourceVar)) {
                indegree.put(targetVar, indegree.get(targetVar) - 1);
                if (indegree.get(targetVar) == 0) {
                    queue.offer(targetVar);
                }
            }
        }
    }
    for (String variable : variables) {
        if (indegree.containsKey(variable) && indegree.get(variable) > 0) {
            logger.warn("variableId = {} is in the cycle,", variable);
            return true;
        }
    }
    return false;
}

判断是否存在循环引用

原文：https://www.cnblogs.com/tommaoxiaoqi/p/12726845.html