content: package at.ac.tuwien.kr.alpha.core.test.util;
  
  import java.util.ArrayList;
  import java.util.HashSet;
  import java.util.List;
  import java.util.Set;
  
  import at.ac.tuwien.kr.alpha.api.programs.analysis.DependencyGraph;
  import at.ac.tuwien.kr.alpha.api.programs.analysis.DependencyGraph.Edge;
  import at.ac.tuwien.kr.alpha.api.programs.analysis.DependencyGraph.Node;
  
  /**
   * 
   * Copyright (c) 2019-2020, the Alpha Team.
   */
  public final class DependencyGraphUtils {
  
  	private DependencyGraphUtils() {
  
  	}
  
  	public static boolean isReachableFrom(Node dest, Node src, DependencyGraph dg) {
  		return DependencyGraphUtils.isReachableFrom(dest, src, dg, new HashSet<>());
  	}
  
  	private static boolean isReachableFrom(Node dest, Node src, DependencyGraph dg, Set<Node> discovered) {
  		List<Edge> outgoingEdges;
  		if (src.equals(dest)) {
  			return true;
  		}
  		if ((outgoingEdges = dg.getAdjancencyMap().get(src)) == null) {
  			return false;
  		}
  		discovered.add(src);
  		// Checking all edges first before descending deeper.
  		for (Edge edge : outgoingEdges) {
  			if (edge.getTarget().equals(dest)) {
  				return true;
  			}
  		}
  		for (Edge tmp : outgoingEdges) {
  			if (discovered.contains(tmp.getTarget())) {
  				// Cycle found, do not descend deeper.
  				continue;
  			}
  			if (DependencyGraphUtils.isReachableFrom(dest, tmp.getTarget(), dg, discovered)) {
  				return true;
  			}
  		}
  		return false;
  	}
  
  	/**
  	 * Checks whether the given nodes are strongly connected within the given dependency graph. Strongly connected
  	 * means every node in the given list is reachable from every other node in the list and vice versa.
  	 * 
  	 * @param connectedNodes the nodes to check.
  	 * @param dg             the dependency graph in which to check.
  	 * @return true if the given nodes are strongly connected, false otherwise.
  	 */
  	public static boolean areStronglyConnected(List<Node> connectedNodes, DependencyGraph dg) {
  		for (Node n1 : connectedNodes) {
  			for (Node n2 : connectedNodes) {
  				if (!(DependencyGraphUtils.isReachableFrom(n2, n1, dg) && DependencyGraphUtils.isReachableFrom(n1, n2, dg))) {
  					return false;
  				}
  			}
  		}
  		return true;
  	}
  
  	public static boolean isStronglyConnectedComponent(List<Node> componentNodes, DependencyGraph dg) {
  		if (!DependencyGraphUtils.areStronglyConnected(componentNodes, dg)) {
  			return false;
  		}
  		// Check if the given set is maximal.
  		List<Node> lst = new ArrayList<>(componentNodes);
  		for (Node n : dg.getAdjancencyMap().keySet()) {
  			if (lst.contains(n)) {
  				continue;
  			}
  			lst.add(n);
  			if (DependencyGraphUtils.areStronglyConnected(lst, dg)) {
  				// Not a strongly connected component if there is a bigger set which is strongly connected.
  				return false;
  			}
  		}
  		return true;
  	}
  
  }
  