I am currently learning about different algorithms demonstrated in the book Algorithm Design by Kleinberg and Tardos. I have completed an implementation of the Kosaraju-Sharir algorithm and I am now attempting to construct a Kernel DAG based on the strongly connected components. I am unsure how to implement code that will perform this. Currently, I have a method titled display that will print the strongly connected components and I want it to be able to print the Kernel DAG as well. Within this code, adjacent is my adjacency list with DFS already performed on the reverse adjacency list. The variable "kern" is just a copy of the initial adjacency list which was input in a format shown below. I would like the output Kernel DAG to look similar, with strongly connected component 1 printed next to the strongly connected component it has an edge with (SCC2 SCC4 for example).
1 0
0 2
2 1
0 3
3 4
The output of the following method with the given input shown below:
The given graph has 3 Strongly Connected Components.
Connected Component #0: [4]
Connected Component #1: [3]
Connected Component #2: [0, 2, 1]
public static void display (ArrayList<ArrayList<Integer>> adjacent, ArrayList<ArrayList<Integer>>kern)
{
Iterator<ArrayList<Integer>> temp = adjacent.iterator();
int size = adjacent.size();
System.out.println("\nThe given graph has " + size + " Strongly Connected Components.");
for(int i = 0; temp.hasNext(); i++)
{
ArrayList<Integer> x = temp.next();
System.out.println("Connected Component #"+i + ":\t" + x);
}
System.out.println(kern);
}
I have attempted to write pseudocode for this issue. I know that since I have my strongly connected components, I can create a for loop that will iterate through each vertex in the individual strongly connected components and look in the original adjacency list for an edge connecting it to another SCC. Also, I believe it may be best practice to implement a hashmap to store the Kernel DAG then checking that hashmap for duplicates before printing. Would that be the best and cleanest method of creating a Kernel DAG? Or is there a better solution that I am missing?
Yes, it is redundant but that would be the only way to check for an edge. Using a topological sort will reduce the time complexity,if you do use a topological sort you need not worry about duplicates.
You can refer to the below for equations as well as hints on Graph Kernels . https://cs.uwaterloo.ca/~y328yu/mycourses/480-2018/assignments/a3/hw3.pdf