Package org.drip.graph.shortestpath

Class FloydWarshallDistanceMatrix

java.lang.Object
org.drip.graph.shortestpath.FloydWarshallDistanceMatrix
public class FloydWarshallDistanceMatrix
extends java.lang.Object
FloydWarshallDistanceMatrix holds the Cross-Vertex Distance Matrix between a Pair of Vertexes. The References are:

  • Chan, T. M. (2010): More Algorithms for All-Pairs Shortest Paths in Weighted Graphs SIAM Journal on Computing 39 (5) 2075-2089
  • Floyd, R. W. (1962): Algorithm 97: Shortest Path Communications of the ACM 5 (6) 345
  • Hougardy, S. (2010): The Floyd-Warshall Algorithm on Graphs with Negative Cycles Information Processing Letters 110 (8-9) 279-291
  • Warshall, S. (1962): A Theorem on Boolean Matrices Journal of the ACM 9 (1) 11-12
  • Wikipedia (2020): Floyd-Warshall Algorithm https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    FloydWarshallDistanceMatrix​(java.util.Map<java.lang.String,​java.lang.Integer> vertexIndexMap, java.util.Map<java.lang.Integer,​java.lang.String> indexVertexMap)
    FloydWarshallDistanceMatrix Constructor

  • Method Summary

    Modifier and Type Method Description
    static FloydWarshallDistanceMatrix FromGraph​(Directed<?> graph)
    Generate a FloydWarshallDistanceMatrix Instance from the specified Graph
    java.util.Map<java.lang.Integer,​java.lang.String> indexVertexMap()
    Retrieve the Index to Vertex Map
    java.util.Map<java.lang.String,​java.lang.Integer> vertexIndexMap()
    Retrieve the Vertex to Index Map

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • FloydWarshallDistanceMatrix

      public FloydWarshallDistanceMatrix​(java.util.Map<java.lang.String,​java.lang.Integer> vertexIndexMap, java.util.Map<java.lang.Integer,​java.lang.String> indexVertexMap) throws java.lang.Exception
      FloydWarshallDistanceMatrix Constructor
      Parameters:
      vertexIndexMap - Vertex to Index Map
      indexVertexMap - Index to Vertex Map
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • FromGraph

      public static final FloydWarshallDistanceMatrix FromGraph​(Directed<?> graph)
      Generate a FloydWarshallDistanceMatrix Instance from the specified Graph
      Parameters:
      graph - The Graph
      Returns:
      FloydWarshallDistanceMatrix Instance

    • vertexIndexMap

      public java.util.Map<java.lang.String,​java.lang.Integer> vertexIndexMap()
      Retrieve the Vertex to Index Map
      Returns:
      Vertex to Index Map

    • indexVertexMap

      public java.util.Map<java.lang.Integer,​java.lang.String> indexVertexMap()
      Retrieve the Index to Vertex Map
      Returns:
      Index to Vertex Map