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}