001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of AutomataLib, http://www.automatalib.net/. 003 * 004 * AutomataLib is free software; you can redistribute it and/or 005 * modify it under the terms of the GNU Lesser General Public 006 * License version 3.0 as published by the Free Software Foundation. 007 * 008 * AutomataLib is distributed in the hope that it will be useful, 009 * but WITHOUT ANY WARRANTY; without even the implied warranty of 010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 011 * Lesser General Public License for more details. 012 * 013 * You should have received a copy of the GNU Lesser General Public 014 * License along with AutomataLib; if not, see 015 * http://www.gnu.de/documents/lgpl.en.html. 016 */ 017package net.automatalib.algorithms.graph.scc; 018 019import java.util.List; 020 021import net.automatalib.graphs.Graph; 022import net.automatalib.util.graphs.traversal.GraphTraversal; 023 024/** 025 * Algorithms for finding strongly-connected components (SCCs) in a graph. 026 * 027 * @author Malte Isberner <malte.isberner@gmail.com> 028 * 029 */ 030public abstract class SCCs { 031 032 private SCCs() { 033 } 034 035 036 /** 037 * Find all strongly-connected components in a graph. When a new SCC is found, the 038 * {@link SCCListener#foundSCC(java.util.Collection)} method is invoked. The listener 039 * object may hence not be null. 040 * <p> 041 * Tarjan's algorithm is used for realizing the SCC search. 042 * 043 * @param graph the graph 044 * @param listener the SCC listener 045 * 046 * @see TarjanSCCVisitor 047 */ 048 public static <N,E> void findSCCs(Graph<N,E> graph, SCCListener<N> listener) { 049 TarjanSCCVisitor<N, E> vis = new TarjanSCCVisitor<>(graph, listener); 050 for(N node : graph) { 051 if(!vis.hasVisited(node)) 052 GraphTraversal.depthFirst(graph, node, vis); 053 } 054 } 055 056 /** 057 * Collects all strongly-connected components in a graph. The SCCs are returned as 058 * a list of lists. 059 * <p> 060 * Tarjan's algorithm is used for realizing the SCC search. 061 * 062 * @param graph the graph 063 * @return a list of all SCCs, each represented as a list of its nodes 064 * 065 * @see TarjanSCCVisitor 066 */ 067 public static <N,E> List<List<N>> collectSCCs(Graph<N,E> graph) { 068 SCCCollector<N> coll = new SCCCollector<>(); 069 findSCCs(graph, coll); 070 return coll.getSCCList(); 071 } 072 073}