Package org.drip.graph.connectivity

Class Kosaraju

java.lang.Object
org.drip.graph.connectivity.Kosaraju
public class Kosaraju
extends java.lang.Object
Kosaraju implements the 2-pass Kosaraju Strongly Connected Components Algorithm. The References are:

  • Aho, A. V., J. E. Hopcroft, and J. D. Ullman (1983): Data Structures and Algorithms Addison Wesley
  • Blelloch, G. E., Y. Gu, J. Shun, and Y. Sun (2016): Parallelism in Randomized Incremental Algorithms Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures 467-478
  • Cormen, T., C. E. Leiserson, R. Rivest, and C. Stein (2009): Introduction to Algorithms 3rd Edition MIT Press
  • Sharir, M. (1981): A Strong-connectivity Algorithm and its Applications to Data Flow Analysis Computer and Mathematics with Applications 7 (1) 67-72
  • Wikipedia (2020): Kosaraju's Algorithm https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    Kosaraju​(Network graph)
    Kosaraju Constructor

  • Method Summary

    Modifier and Type Method Description
    Network graph()
    Retrieve the Network Graph
    java.util.Map<java.lang.String,​java.lang.String> vertexRootComponentMap()
    Compute the Vertex Root Component Map

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • Kosaraju

      public Kosaraju​(Network graph) throws java.lang.Exception
      Kosaraju Constructor
      Parameters:
      graph - The Graph Network
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • graph

      public Network graph()
      Retrieve the Network Graph
      Returns:
      The Network Graph

    • vertexRootComponentMap

      public java.util.Map<java.lang.String,​java.lang.String> vertexRootComponentMap()
      Compute the Vertex Root Component Map
      Returns:
      The Vertex Root Component Map