import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; class ServiceGraph { private final Map> deps = new HashMap<>(); void addDependency(String from, String to) { deps.computeIfAbsent(from, k -> new ArrayList<>()).add(to); deps.computeIfAbsent(to, k -> new ArrayList<>()); } // True if the dependency graph contains a cycle. boolean hasCycle() { Set visited = new HashSet<>(); Set inStack = new HashSet<>(); for (String node : deps.keySet()) { if (dfs(node, visited, inStack)) { return true; } } return false; } private boolean dfs(String node, Set visited, Set inStack) { if (inStack.contains(node)) { return true; } if (visited.contains(node)) { return false; } visited.add(node); inStack.add(node); for (String next : deps.get(node)) { if (dfs(next, visited, inStack)) { return true; } } inStack.remove(node); return false; } } public class Main { public static void main(String[] args) { ServiceGraph clean = new ServiceGraph(); clean.addDependency("Order", "Payment"); clean.addDependency("Order", "Inventory"); clean.addDependency("Payment", "Ledger"); System.out.println("Clean graph has cycle: " + clean.hasCycle()); ServiceGraph tangled = new ServiceGraph(); tangled.addDependency("Order", "Payment"); tangled.addDependency("Payment", "Inventory"); tangled.addDependency("Inventory", "Order"); // loops back to Order System.out.println("Tangled graph has cycle: " + tangled.hasCycle()); } }

Premium Content

Get Premium