如何检测集合中的循环

Question

与 How to find if a graph has a cycle? 类似，但更符合标准 Java Set

我有一项 class 技能，它具有先决条件技能。

@Data
@Entity
public class Skill {
    @Id
    @GeneratedValue
    private UUID id;

    @OneToMany
    private Set<Skill> prerequisites = new HashSet<>();
    private String name;

}

我想确保先决条件中没有循环。

这就是我的开始，当然它不起作用，因为我只真正处理了自循环。

@UtilityClass
public class CycleChecks {
    /**
     * Take a root object and a function to get its edges to see if there are any cycles.
     *
     * @param root  root object
     * @param edges a function that would take an object and get its edges.
     * @param <T>   an object that has edges
     * @return has a cycle.
     */
    public <T> boolean isCyclic(T root, Function<T, Iterable<T>> edges) {
        final Set<T> visited = new HashSet<>();
        return doIsCyclic(root, edges, visited);
    }

    private <T> boolean doIsCyclic(T vertex, Function<T, Iterable<T>> edges, Set<T> visited) {
        if (visited.contains(vertex)) {
            return true;
        }
        visited.add(vertex);
        for (T edgeTarget : edges.apply(vertex)) {
            if (doIsCyclic(edgeTarget, edges, visited)) {
                return true;
            }
        }
        return false;
    }
}

Answer 1

像下面这样的东西很好，没有彻底测试它。只有一个保留 ID 的列表，我们可能会遇到这样一种情况，即多个单独的技能具有相同的先决条件，并且它被错误地检测为一个循环。例如，这里发生这种情况：keycloak aggregated policies.，因此使用第二个递归列表。

你调用它：hasCycle(yourFirstSkill, new ArrayList<>(), new ArrayList<>());

public static boolean hasCycle(Skill entry, List<UUID> visited, List<UUID> recursion) {
  UUID currentId = entry.getId();

  if (recursion.contains(currentId))
    return true;

  if (visited.contains(currentId))
    return false;

  visited.add(currentId);
  recursion.add(currentId);

  for (final Skill prerequisite : entry.getPrerequisites()) {
    if (hasCycle(prerequisite, visited, recursion)) {
      return true;
    }
  }

  recursion.remove(currentId);

  return false;
}

Answer 2

我的最终解决方案基于@Shadov 的回答。只是做了一些调整使其通用，我将 Set 用于 visited 和 recursion 而不是列表。

@UtilityClass
public class CycleChecks {
    /**
     * Take a root object and a function to get its edges to see if there are any cycles.
     *
     * @param root             root object
     * @param adjacentFunction a function that would take an object and return an iterable of objects that are adjacent to it.
     * @param <T>              an object that has edges
     * @return has a cycle.
     */
    public <T> boolean isCyclic(T root, Function<T, Iterable<T>> adjacentFunction) {
        final Set<T> visited = new HashSet<>();
        final Set<T> recursion = new HashSet<>();
        return doIsCyclic(root, adjacentFunction, visited, recursion);
    }

    private <T> boolean doIsCyclic(T current, Function<T, Iterable<T>> adjacentFunction, Set<T> visited, Set<T> recursion) {
        if (recursion.contains(current)) {
            return true;
        }
        if (visited.contains(current)) {
            return false;
        }
        visited.add(current);
        recursion.add(current);
        for (T adjacent : adjacentFunction.apply(current)) {
            if (doIsCyclic(adjacent, adjacentFunction, visited, recursion)) {
                return true;
            }
        }
        recursion.remove(current);
        return false;
    }

}

并且通过 non-scientific 方法通过删除递归稍微快了 5 毫秒。

@UtilityClass
public class CycleChecks {
    /**
     * Take a root object and a function to get its edges to see if there are any cycles.
     *
     * @param root             root object
     * @param adjacentFunction a function that would take an object and return an iterable of objects that are adjacent to it.
     * @param <T>              an object that has edges
     * @return has a cycle.
     */
    public <T> boolean isCyclic(T root, Function<T, Iterable<T>> adjacentFunction) {
        final Set<T> visited = new HashSet<>();
        final Deque<T> recursion = new LinkedList<>();
        final Deque<Node<T>> nodesToVisit = new LinkedList<>();
        final Node<T> popRecursionNode = new Node<>();
        nodesToVisit.add(new Node<>(root));

        while (!nodesToVisit.isEmpty()) {
            final Node<T> frontOfQueue = nodesToVisit.pop();
            if (frontOfQueue.isPopRecursion()) {
                recursion.pop();
                continue;
            }
            T current = frontOfQueue.getObj();
            if (recursion.contains(current)) {
                return true;
            }
            if (visited.contains(current)) {
                continue;
            }
            visited.add(current);
            recursion.push(current);
            for (T adjacent : adjacentFunction.apply(current)) {
                nodesToVisit.add(new Node<>(adjacent));
            }
            nodesToVisit.add(popRecursionNode);

        }
        return false;
    }

    @Data
    private static class Node<T> {
        private final T obj;
        private final boolean popRecursion;

        public Node(T obj) {
            this.obj = obj;
            popRecursion = false;
        }

        public Node() {
            obj = null;
            popRecursion = true;
        }
    }

如何检测集合中的循环

How to detect cycles in sets

java

graph-theory