Saturday, May 23, 2015

Strongly Connected Components : Kosaraju’s algorithm Implementation - Java

Helpful links for algorithm exaplanation :


Source:

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class KosarajuSharirStronglyConnectedComponents {
    static int V, E;
    static ArrayList<ArrayList<Integer>> G = new ArrayList<>(); 
    static ArrayList<ArrayList<Integer>> GD = new ArrayList<>(); 
    
    static ArrayList<Integer> sortOrder = new ArrayList<>();
    
    static boolean marked[];
    static int reg[];
    static int groupNo=0;
    
    static void dfs(int vertex){
        if(marked[vertex])return;
        
        marked[vertex] = true;
        
        for(int c:G.get(vertex)){
            dfs(c);
        } 
        sortOrder.add(vertex);
    }
    
    static void dfs2(int vertex){
        if(marked[vertex])return;
        
        marked[vertex] = true;
        
        for(int c:GD.get(vertex)){
            dfs2(c); 
        }
        reg[vertex] = groupNo;
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new FileReader("e:\\inputVideo.txt"));
        String s = null;
        
        V = Integer.parseInt(br.readLine());
        E = Integer.parseInt(br.readLine());
        
        marked = new boolean[V];
        reg = new int[V];
        
        for(int i=0;i<V;++i){G.add(new ArrayList<>());GD.add(new ArrayList<>());}
        
        while((s=br.readLine())!=null){
            String d[] = s.split(" ");
            int from, to;
            from = Integer.parseInt(d[0]);
            to = Integer.parseInt(d[1]);
            
            G.get(from).add(to);
            GD.get(to).add(from);
        }
        
        for(int i=0;i<V;++i){
            dfs(i);
        }
        
        System.out.println(sortOrder); 
        Collections.reverse(sortOrder);
        
        Arrays.fill(marked, false); 
        
        for(int i:sortOrder){
            if(!marked[i])groupNo++;
            dfs2(i); 
        }
        
        for(int i=0;i<reg.length;++i){
            System.out.println("Node "+i+" group = "+reg[i]);
        }
    } 
}

Input Format:

Number of vertices V
Number of edges     E
Directed edges Node-from to Node-to
.
.
.
Eth edge

Input File (2 tests):



File #1 Contents:

13
20
0 1
0 5
2 0
2 3
3 2
3 5
4 2
6 0
6 8
6 4
6 9
7 6
7 9
8 6
9 10
9 11
10 12
11 12
11 4
12 9

File #2 Contents (Example case geeksforgeeks):

5
5
1 0
0 2
2 1
0 3
3 4



Output:

For Test #1:

[1, 2, 4, 3, 0]
Node 0 group = 1
Node 1 group = 1
Node 2 group = 1
Node 3 group = 2
Node 4 group = 3


For Test #2:

[1, 5, 0, 3, 2, 4, 8, 12, 10, 11, 9, 6, 7]
Node 0 group = 6
Node 1 group = 8
Node 2 group = 5
Node 3 group = 5
Node 4 group = 4
Node 5 group = 7
Node 6 group = 2
Node 7 group = 1
Node 8 group = 2
Node 9 group = 3
Node 10 group = 3
Node 11 group = 3
Node 12 group = 3

Practice problems: SPOJ: http://www.spoj.com/problems/WEBISL/

Solution :Java: AC:

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class WEBISL {
    static int V, E;
    static ArrayList<ArrayList<Integer>> G = new ArrayList<>(); 
    static ArrayList<ArrayList<Integer>> GD = new ArrayList<>(); 
    
    static ArrayList<Integer> sortOrder = new ArrayList<>();
    
    static boolean marked[];
    static int reg[];
    static int groupNo=-1;
    
    static void dfs(int vertex){
        if(marked[vertex])return;
        
        marked[vertex] = true;
        
        for(int c:G.get(vertex)){
            dfs(c);
        } 
        sortOrder.add(vertex);
    }
    static int[] groups;
    static void dfs2(int vertex){
        if(marked[vertex])return;
        
        marked[vertex] = true;
        
        for(int c:GD.get(vertex)){
            dfs2(c); 
        }
        if(groups[groupNo]>vertex)groups[groupNo]=vertex;
        reg[vertex] = groupNo;
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = null;
        
        String[] fD = br.readLine().split(" ");
        V = Integer.parseInt(fD[0]);
        E = Integer.parseInt(fD[1]);
        groups = new int[V];
        Arrays.fill(groups, Integer.MAX_VALUE);
        marked = new boolean[V];
        reg = new int[V];
        
        for(int i=0;i<V;++i){G.add(new ArrayList<>());GD.add(new ArrayList<>());}
        
        while(E-->0){
            s = br.readLine();
            String d[] = s.split(" ");
            int from, to;
            from = Integer.parseInt(d[0]);
            to = Integer.parseInt(d[1]);
            
            G.get(from).add(to);
            GD.get(to).add(from);
        }
        
        for(int i=0;i<V;++i){
            dfs(i);
        }
        
//        System.out.println(sortOrder); 
        Collections.reverse(sortOrder);
        
        Arrays.fill(marked, false); 
        
        for(int i:sortOrder){
            if(!marked[i]){groupNo++;}
            dfs2(i); 
        }
         
        for(int i=0;i<reg.length;++i){
            System.out.println(groups[reg[i]]);
        }
//        System.out.println(Arrays.toString(groups));
//        System.out.println(Arrays.toString(reg));
    } 
}

No comments:

Post a Comment