Class FloydWarshallShortestPaths<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    @Deprecated
    public class FloydWarshallShortestPaths<V,​E>
    extends java.lang.Object
    Deprecated.
    The Floyd-Warshall algorithm finds all shortest paths (all n^2 of them) in O(n^3) time. It can also calculate the graph diameter. Note that during construction time, no computations are performed! All computations are performed the first time one of the member methods of this class is invoked. The results are stored, so all subsequent calls to the same method are computationally efficient. Warning: This code has not been tested (and probably doesn't work) on multi-graphs. Code should be updated to work properly on multi-graphs.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private int[][] backtrace
      Deprecated.
       
      private double[][] d
      Deprecated.
       
      private double diameter
      Deprecated.
       
      private Graph<V,​E> graph
      Deprecated.
       
      private int[][] lastHopMatrix
      Deprecated.
       
      private int nShortestPaths
      Deprecated.
       
      private java.util.Map<V,​java.util.List<GraphPath<V,​E>>> paths
      Deprecated.
       
      private java.util.Map<V,​java.lang.Integer> vertexIndices
      Deprecated.
       
      private java.util.List<V> vertices
      Deprecated.
       
    • Constructor Summary

      Constructors 
      Constructor Description
      FloydWarshallShortestPaths​(Graph<V,​E> graph)
      Deprecated.
      Create a new instance of the Floyd-Warshall all-pairs shortest path algorithm.
    • Method Summary

      All Methods Instance Methods Concrete Methods Deprecated Methods 
      Modifier and Type Method Description
      double getDiameter()
      Deprecated.
       
      V getFirstHop​(V a, V b)
      Deprecated.
      Returns the first hop, i.e., the second node on the shortest path from a to b.
      Graph<V,​E> getGraph()
      Deprecated.
       
      V getLastHop​(V a, V b)
      Deprecated.
      Returns the last hop, i.e., the second to last node on the shortest path from a to b.
      GraphPath<V,​E> getShortestPath​(V a, V b)
      Deprecated.
      Get the shortest path between two vertices.
      java.util.List<V> getShortestPathAsVertexList​(V a, V b)
      Deprecated.
      Get the shortest path between two vertices as a list of vertices.
      java.util.List<GraphPath<V,​E>> getShortestPaths()
      Deprecated.
      Get all shortest paths in the graph.
      java.util.List<GraphPath<V,​E>> getShortestPaths​(V v)
      Deprecated.
      Get shortest paths from a vertex to all other vertices in the graph.
      int getShortestPathsCount()
      Deprecated.
       
      private void lazyCalculateMatrix()
      Deprecated.
      Calculates the matrix of all shortest paths, but does not populate the paths map.
      private void lazyCalculatePaths()
      Deprecated.
      Calculate the shortest paths (not done per default) TODO: This method can be optimized.
      private void populateLastHopMatrix()
      Deprecated.
      Populate the last hop matrix, using the earlier computed backtrace matrix.
      double shortestDistance​(V a, V b)
      Deprecated.
      Get the length of a shortest path.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • graph

        private final Graph<V,​E> graph
        Deprecated.
      • vertices

        private final java.util.List<V> vertices
        Deprecated.
      • vertexIndices

        private final java.util.Map<V,​java.lang.Integer> vertexIndices
        Deprecated.
      • nShortestPaths

        private int nShortestPaths
        Deprecated.
      • diameter

        private double diameter
        Deprecated.
      • d

        private double[][] d
        Deprecated.
      • backtrace

        private int[][] backtrace
        Deprecated.
      • lastHopMatrix

        private int[][] lastHopMatrix
        Deprecated.
      • paths

        private java.util.Map<V,​java.util.List<GraphPath<V,​E>>> paths
        Deprecated.
    • Constructor Detail

      • FloydWarshallShortestPaths

        public FloydWarshallShortestPaths​(Graph<V,​E> graph)
        Deprecated.
        Create a new instance of the Floyd-Warshall all-pairs shortest path algorithm.
        Parameters:
        graph - the input graph
    • Method Detail

      • getGraph

        public Graph<V,​E> getGraph()
        Deprecated.
        Returns:
        the graph on which this algorithm operates
      • getShortestPathsCount

        public int getShortestPathsCount()
        Deprecated.
        Returns:
        total number of shortest paths
      • lazyCalculateMatrix

        private void lazyCalculateMatrix()
        Deprecated.
        Calculates the matrix of all shortest paths, but does not populate the paths map.
      • shortestDistance

        public double shortestDistance​(V a,
                                       V b)
        Deprecated.
        Get the length of a shortest path.
        Parameters:
        a - first vertex
        b - second vertex
        Returns:
        shortest distance between a and b
      • getDiameter

        public double getDiameter()
        Deprecated.
        Returns:
        the diameter (longest of all the shortest paths) computed for the graph. If the graph is vertexless, return 0.0.
      • getShortestPath

        public GraphPath<V,​E> getShortestPath​(V a,
                                                    V b)
        Deprecated.
        Get the shortest path between two vertices.
        Parameters:
        a - from vertex
        b - to vertex
        Returns:
        the path, or null if none found
      • getShortestPathAsVertexList

        public java.util.List<V> getShortestPathAsVertexList​(V a,
                                                             V b)
        Deprecated.
        Get the shortest path between two vertices as a list of vertices.
        Parameters:
        a - from vertex
        b - to vertex
        Returns:
        the path, or null if none found
      • getShortestPaths

        public java.util.List<GraphPath<V,​E>> getShortestPaths​(V v)
        Deprecated.
        Get shortest paths from a vertex to all other vertices in the graph.
        Parameters:
        v - the originating vertex
        Returns:
        List of paths
      • getShortestPaths

        public java.util.List<GraphPath<V,​E>> getShortestPaths()
        Deprecated.
        Get all shortest paths in the graph.
        Returns:
        List of paths
      • getFirstHop

        public V getFirstHop​(V a,
                             V b)
        Deprecated.
        Returns the first hop, i.e., the second node on the shortest path from a to b. Lookup time is O(1). If the shortest path from a to b is a,c,d,e,b, this method returns c. If the next invocation would query the first hop on the shortest path from c to b, vertex d would be returned, etc. This method is computationally cheaper than getShortestPathAsVertexList(a,b).get(0);
        Parameters:
        a - source vertex
        b - target vertex
        Returns:
        next hop on the shortest path from a to b, or null when there exists no path from a to b.
      • getLastHop

        public V getLastHop​(V a,
                            V b)
        Deprecated.
        Returns the last hop, i.e., the second to last node on the shortest path from a to b. Lookup time is O(1). If the shortest path from a to b is a,c,d,e,b, this method returns e. If the next invocation would query the next hop on the shortest path from c to e, vertex d would be returned, etc. This method is computationally cheaper than getShortestPathAsVertexList(a,b).get(shortestPathListSize-1);. The first invocation of this method populates a last hop matrix.
        Parameters:
        a - source vertex
        b - target vertex
        Returns:
        last hop on the shortest path from a to b, or null when there exists no path from a to b.
      • populateLastHopMatrix

        private void populateLastHopMatrix()
        Deprecated.
        Populate the last hop matrix, using the earlier computed backtrace matrix.
      • lazyCalculatePaths

        private void lazyCalculatePaths()
        Deprecated.
        Calculate the shortest paths (not done per default) TODO: This method can be optimized. Instead of calculating each path individidually, use a constructive method. TODO: I.e. if we have a shortest path from i to j: [i,....j] and we know that the shortest path from j to k, we can simply glue the paths together to obtain the shortest path from i to k