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}