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;
018
019import java.util.ArrayList;
020import java.util.List;
021
022import net.automatalib.algorithms.graph.apsp.APSPResult;
023import net.automatalib.algorithms.graph.apsp.FloydWarshallAPSP;
024import net.automatalib.algorithms.graph.scc.SCCListener;
025import net.automatalib.algorithms.graph.scc.SCCs;
026import net.automatalib.algorithms.graph.scc.TarjanSCCVisitor;
027import net.automatalib.algorithms.graph.sssp.DijkstraSSSP;
028import net.automatalib.algorithms.graph.sssp.SSSPResult;
029import net.automatalib.graphs.Graph;
030import net.automatalib.graphs.concepts.EdgeWeights;
031
032/**
033 * Convenience entry points and helper methods for various graph algorithms.
034 * 
035 * @author Malte Isberner <malte.isberner@gmail.com>
036 *
037 */
038public class GraphAlgorithms {
039
040        /**
041         * Float value to signal that no valid distance is returned (e.g., when attempting
042         * to retrieve the length of a path that does not exist).
043         */
044        public static final float INVALID_DISTANCE = Float.NEGATIVE_INFINITY;
045        
046        
047        /**
048         * Converts a list of edges into a corresponding list of nodes. Note that the
049         * list of nodes is always one larger than the respective list of edges.
050         * 
051         * @param edgeList the list of edges
052         * @param graph the graph
053         * @param init the initial node
054         * @return the node list corresponding to the given edge list.
055         */
056        public static <N,E> List<N> toNodeList(List<E> edgeList, Graph<N,E> graph, N init) {
057                List<N> result = new ArrayList<>(edgeList.size() + 1);
058                result.add(init);
059                
060                for(E edge : edgeList) {
061                        N tgt = graph.getTarget(edge);
062                        result.add(tgt);
063                }
064                
065                return result;
066        }
067        
068        
069        /**
070         * Computes the shortest paths between all pairs of nodes in a graph, using the
071         * Floyd-Warshall dynamic programming algorithm. Note that the result is only correct
072         * if the graph contains no cycles with negative edge weight sums.
073         * @param graph the graph
074         * 
075         * @param edgeWeights the edge weights 
076         * @return the all pairs shortest paths result
077         * @see FloydWarshallAPSP
078         */
079        public static <N,E> APSPResult<N,E> findAPSP(Graph<N,E> graph, EdgeWeights<E> edgeWeights) {
080                return FloydWarshallAPSP.findAPSP(graph, edgeWeights);
081        }
082        
083        /**
084         * Computes the shortest paths between a single source node and all other nodes in a graph,
085         * using Dijkstra's algorithm. Note that the result is only correct if the graph contains
086         * no edges with negative weights.
087         * 
088         * @param graph the graph
089         * @param init the source node
090         * @param edgeWeights the edge weights
091         * @return the single-source shortest paths result
092         * @see DijkstraSSSP
093         */
094        public static <N,E> SSSPResult<N,E> findSSSP(Graph<N,E> graph, N init, EdgeWeights<E> edgeWeights) {
095                return DijkstraSSSP.findSSSP(graph, init, edgeWeights);
096        }
097
098        /**
099         * Collects all strongly-connected components in a graph. The SCCs are returned as
100         * a list of lists.
101         * <p>
102         * Tarjan's algorithm is used for realizing the SCC search.
103         * 
104         * @param graph the graph
105         * @return a list of all SCCs, each represented as a list of its nodes
106         * 
107         * @see TarjanSCCVisitor
108         * @see SCCs
109         */
110        public static <N,E> List<List<N>> collectSCCs(Graph<N,E> graph) {
111                return SCCs.collectSCCs(graph);
112        }
113        
114        /**
115         * Find all strongly-connected components in a graph. When a new SCC is found, the
116         * {@link SCCListener#foundSCC(java.util.Collection)} method is invoked. The listener
117         * object may hence not be null.
118         * <p>
119         * Tarjan's algorithm is used for realizing the SCC search.
120         * 
121         * @param graph the graph
122         * @param listener the SCC listener
123         * 
124         * @see TarjanSCCVisitor
125         * @see SCCs
126         */
127        public static <N,E> void findSCCs(Graph<N,E> graph, SCCListener<N> sccListener) {
128                SCCs.findSCCs(graph, sccListener);
129        }
130}