Reputation: 41450
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
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
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