001/*
002 * JDrupes Builder
003 * Copyright (C) 2026 Michael N. Lipp
004 * 
005 * This program is free software: you can redistribute it and/or modify
006 * it under the terms of the GNU Affero General Public License as
007 * published by the Free Software Foundation, either version 3 of the
008 * License, or (at your option) any later version.
009 *
010 * This program is distributed in the hope that it will be useful,
011 * but WITHOUT ANY WARRANTY; without even the implied warranty of
012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
013 * GNU Affero General Public License for more details.
014 *
015 * You should have received a copy of the GNU Affero General Public License
016 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
017 */
018
019package org.jdrupes.builder.core;
020
021import java.util.ArrayList;
022import java.util.HashMap;
023import java.util.HashSet;
024import java.util.List;
025import java.util.Map;
026import java.util.Set;
027
028/// The Class CycleDetection.
029///
030public class CycleDetection {
031
032    public record Edge(ProviderInvocation<?> caller, ProviderInvocation<?> callee) {
033    }
034
035    public static boolean hasCycle(List<Edge> edges) {
036        // Step 1: Build adjacency list
037        Map<ProviderInvocation<?>, List<ProviderInvocation<?>>> graph = new HashMap<>();
038
039        for (Edge edge : edges) {
040            graph.computeIfAbsent(edge.caller, k -> new ArrayList<>())
041                .add(edge.callee);
042            graph.computeIfAbsent(edge.callee, k -> new ArrayList<>());
043        }
044
045        // Step 2: DFS cycle detection
046        Set<ProviderInvocation<?>> visited = new HashSet<>();
047        Set<ProviderInvocation<?>> inStack = new HashSet<>();
048
049        for (ProviderInvocation<?> node : graph.keySet()) {
050            if (visited.contains(node)) {
051                continue;
052            }
053            if (dfs(node, graph, visited, inStack)) {
054                return true;
055            }
056        }
057        return false;
058    }
059
060    private static boolean dfs(ProviderInvocation<?> node, Map<ProviderInvocation<?>, List<ProviderInvocation<?>>> graph,
061            Set<ProviderInvocation<?>> visited, Set<ProviderInvocation<?>> inStack) {
062
063        visited.add(node);
064        inStack.add(node);
065
066        for (ProviderInvocation<?> neighbor : graph.get(node)) {
067            if (!visited.contains(neighbor)) {
068                if (dfs(neighbor, graph, visited, inStack)) {
069                    return true;
070                }
071            } else if (inStack.contains(neighbor)) {
072                return true;
073            }
074        }
075
076        inStack.remove(node);
077        return false;
078    }
079
080}