Archimedes Trajano
Archimedes Trajano

Reputation: 41450

How to detect cycles in sets

Similar to How to find if a graph has a cycle? but more for the standard Java Set

I have a class Skill which has prerequisite skills.

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

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

}

I want to make sure that there's no cycles in the prerequisites.

This is what I started out with of course it doesn't work since I only really handled self-cycles.

@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;
    }
}

Upvotes: 0

Views: 335

Answers (2)

Archimedes Trajano
Archimedes Trajano

Reputation: 41450

My final solution based on @Shadov's answer. Just made a few tweaks to make it generic and I used Set for visited and recursion rather than a list.

@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;
    }

}

And a slightly faster by 5ms through non-scientific methods by removing 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 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;
        }
    }

Upvotes: 0

Shadov
Shadov

Reputation: 5592

Something like below is fine, didn't test it that thoroughly tho. With only one list that keeps ID's, we could have a case where multiple separate skills have the same prerequisite and it's detected as a cycle, incorrectly. This happens here for example: keycloak aggregated policies., so second recursion list is used.

You call it with: 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;
}

Upvotes: 1

Related Questions