Question

Create Kernel of a Strongly Connected Components using Kosaraju's Algorithm in Java.

I have to create a Kernel DAG using the Strongly Connected Components found using Kosaraju's Algorithm. The input to the code is in the format.

5 \n 5 \n 1 0 \n 0 2 \n 2 1 \n 0 3 \n 3 4

The code will find the SCCs and print them to the screen, however, I need to find a way to construct a kernel based on these SCCs, so that the output will look like the following:

[0,1,2] [3]

[3] [4]

Due to the fact that the SCCs of [0,1,2] have an edge with SCC [3] and so on.

import java.util.*;

public class Scc {

   public static Scanner kbd = new Scanner (System.in);
   public static int Vnum; // No. of vertices
   public static int Enum;   // No. of vertices
   public static void mkAdj(ArrayList<ArrayList<Integer>> adj)
   {
       System.out.println("Enter data in the following format:\n");
       System.out.println("n -number of vertices \ne -number of edges");
       System.out.println("a1 b1 -represents an edge \na2 b2 \na3 b3 \n.\n.\n.\nae be\n");
       Vnum = kbd.nextInt(); // number of vertices.
       Enum = kbd.nextInt(); // number of edges.

       for(int i = 0; i < Vnum; i++)
       {
           ArrayList<Integer> T = new ArrayList<Integer>();
           adj.add(T);
       }

       // loop to acquire the vertices from the user.
       for(int i = 0; i < Enum; i++)
       {
           int tempX = kbd.nextInt();// vertex 1
           int tempY = kbd.nextInt();// vertex 2
           ArrayList<Integer> point = adj.get(tempX);
           point.add(tempY);
       }

   }
   public static ArrayList<Integer> dfs (ArrayList<ArrayList<Integer>> adj)
   {
       boolean[] visit = new boolean[Vnum];
       Stack<Integer> stack = new Stack<Integer>();
       ArrayList<Integer> stackRev = new ArrayList<Integer>();

       // set all values to false
       for(int i = 0; i < Vnum; i++)
       {
           visit[i]=false;
       }

       while(true)
       {
           int go = notVisited(visit);
           if(go != -1)
           {
               stack.push(go);
               visit[go] = true;
               while(!stack.isEmpty())
               {
                   int top = stack.peek();
                   Iterator<Integer> iter = adj.get(top).iterator();

                   while(true)
                   {
                       if(iter.hasNext())
                       {
                           int nx = iter.next();
                           if(visit[nx] == false)
                           {
                               stack.push(nx);
                               visit[nx] = true;
                               break;
                           }
                       }
                       else
                       {
                           stackRev.add(0,stack.pop());
                           break;
                       }
                   }
               }
           }
           else
           {
               break;
           }
       }

       return stackRev;
}
   public static ArrayList<ArrayList<Integer>> dfsPost (ArrayList<ArrayList<Integer>> adj, ArrayList<Integer> dfs)
   {
       ArrayList<ArrayList<Integer>> connected = new ArrayList<ArrayList<Integer>>();
       boolean[] visit = new boolean[Vnum];
       Stack<Integer> stack = new Stack<Integer>();
       Iterator<Integer> iter1 = dfs.iterator(), iter2;
       int nx1, nx2;

       for(int i = 0; i < Vnum; i++)
       {
           visit[i]=false;
       }

       while(iter1.hasNext())
       {
           nx1 = iter1.next();
           if(!visit[nx1])
           {
               stack.push(nx1);
               visit[nx1] = true;

               ArrayList<Integer> temp = new ArrayList<Integer>();
               connected.add(temp);

               temp.add(nx1);
               while(!stack.isEmpty())
               {
                   int top = stack.peek();
                   iter2 = adj.get(top).iterator();
                   while(true)
                   {
                       if(iter2.hasNext())
                       {
                           nx2 = iter2.next();  
                           if(!visit[nx2])
                           {
                               stack.push(nx2);
                               temp.add(nx2);
                               visit[nx2] = true;
                               break;
                           }
                       }
                       else
                       {
                           stack.pop();
                           break;
                       }
                   }
               }

           }

       }
       return connected;

   }
   public static void display (ArrayList<ArrayList<Integer>> adj)
   {
       Iterator<ArrayList<Integer>> temp = adj.iterator();
       int size = adj.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);
       }

}

public static void main(String[] args)
   {

       // creates the Adjacency list.
       ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
       mkAdj(adj);

       // creates the reverse Adjacency List.
       ArrayList<ArrayList<Integer>> revAdj = mkReverseAdj(adj);
       ArrayList<Integer> x = dfs(revAdj);
      
       display(dfsPost(adj,x));
   }

Answer 1

Do a topological sort, run through the vertices left to right. If 'v' is not black, mark it as black, put it in the kernel, and mark all its' neighbours as black (as in <v,u>∈E<v,u>∈E). Continue until you finish the sort.

topological sort will make your code more elegant easy to read.

If Kosaraju's is used , then your code works fine but i believe using a adjacency matrix would be better for faster lookup to check if 2 SCCs are connected by an edge and form a kernel.

i would be efficient if you check the connectivity while traversing the stack for DFS in reversed graph, beacuse then you know this vertex on stack if its not visited is start node for current SCC and when you come back after peerforming DFS, again when you get a unvisited node , its a start node, just check here , previous start node and this one for connectivity.

All the start nodes visited till now can be hashed .

i believe this should work.