// StrongConnectivity.java
// Sarah Komla-Ebri, Joris Kinable, Hannes Wellmann, 2021
// Modified by Andrew Davison, ad@coe.psu.ac.th, Jan. 2023

/* Utilizes the KosarajuStrongConnectivityInspector class (or 
   GabowStrongConnectivityInspector if uncommented) to compute
   the strongly connected components (SCC) of a directed graph.

   For related code, see Connectivity.java

  Usage:
    > compile StrongConnectivity.java
    > run StrongConnectivity
*/


import org.jgrapht.*;
import org.jgrapht.graph.*;
import org.jgrapht.util.*;

import org.jgrapht.alg.interfaces.*;
import org.jgrapht.alg.connectivity.*;

import java.util.*;



public class StrongConnectivity
{

  public static void main(String args[])
  {
    SCC1();
    SCC2();
  }  // end of main()


  private static void SCC1()
  {
    System.out.println("\n----------- SSC 1 ----------------");

    Graph<String, DefaultEdge> g = 
                    new DefaultDirectedGraph<>(DefaultEdge.class);
    g.addVertex("v1");
    g.addVertex("v2");
    g.addVertex("v3");
    g.addVertex("v4");

    g.addEdge("v1", "v2");
    g.addEdge("v2", "v1");     // strongly connected

    g.addEdge("v4", "v3");     // only weakly connected
    g.addEdge("v3", "v2");     // only weakly connected
   
    System.out.println("Adj List:\n" + JGTUtils.writeAdjList(g));
    JGTUtils.displayAsDOT("SCC1 graph", g);

    findConnections(g);      // reports {V1, V2}, {V3}, {V4}
  } /* SCC1 */



  private static void SCC2()
  {
    System.out.println("\n----------- SCC 2 ----------------");
    Graph<String, DefaultEdge> g = 
                    new DefaultDirectedGraph<>(DefaultEdge.class);
    g.addVertex("v1");
    g.addVertex("v2");
    g.addVertex("v3");
    g.addVertex("v4");

    g.addEdge("v1", "v2");
    g.addEdge("v2", "v3");
    g.addEdge("v3", "v1");     // strongly connected

    g.addEdge("v1", "v4");
    g.addEdge("v2", "v4");
    g.addEdge("v3", "v4");     // weakly connected

    System.out.println("Adj List:\n" + JGTUtils.writeAdjList(g));
    JGTUtils.displayAsDOT("SCC2 graph", g);

    findConnections(g);    // reports {V1, V2, V3}, {V4}
  } /* SCC2 */



  private static <V, E> void findConnections(Graph<V, E> g)
  {
    StrongConnectivityAlgorithm<V, E> inspector = 
         new KosarajuStrongConnectivityInspector<V,E>(g);
        // new GabowStrongConnectivityInspector<V,E>(g);
               // -- uncomment one of these lines

    System.out.println("SC Sets: " + inspector.stronglyConnectedSets());

    System.out.println("SC Components:");
    for (Graph<V, E> sg : inspector.getStronglyConnectedComponents())
      System.out.println(" " + sg);
  }  // end of findConnections()


}  // end of StrongConnectivity class