2 Replies - 680 Views - Last Post: 04 June 2014 - 10:37 AM Rate Topic: -----

#1 google_interview  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 49
  • Joined: 27-December 13

Kosaraju's algorithm: Stackoverflow error

Posted 04 June 2014 - 05:44 AM

Hello all! :bigsmile:


I am currently implementing the infamous Kosaraju algorithm for computing the top 5 strongly connected components in a directed graph.

Given an input file: Get input file here

Quote

The file contains the edges of a directed graph. Vertices are labeled as positive integers from 1 to 875714. Every row indicates an edge, the vertex label in first column is the tail and the vertex label in second column is the head (recall the graph is directed, and the edges are directed from the first column vertex to the second column vertex). So for example, the 11th row looks like : "2 47646". This just means that the vertex with label 2 has an outgoing edge to the vertex with label 47646


Output Format:
Output the sizes of the 5 largest SCCs in the given graph, in decreasing order of sizes, separated by commas.


I get an implementation error for StackOverflow if I use the full input file size. However, if I reduce it to only a few lines things work out! So clearly - the array is not able to hold all the numbers in the input file!

Quote

Exception in thread "main" java.lang.StackOverflowError
at Kosaraju.dfs(Kosaraju.java:61)
at Kosaraju.dfs(Kosaraju.java:67)




The main variables are:

    static int[] fiveLargestSCCs = {0, 0, 0, 0, 0};										// this array will be modified
    static int n = 875714;																// total # of vertices in graph
    static int timer = 0;
    static boolean[] isExplored;														// array holding marked vertices
    static int[] markGraph = new int[n+1];
    static int countSCC;
    static Map<Integer, List<Integer>> adj = new HashMap<Integer, List<Integer>>();		// adjacency list of G
    static Map<Integer, List<Integer>> revAdj = new HashMap<Integer, List<Integer>>();	// adjacency list of reversed G




Read input file into adjacency lists and perform Kosaraju on graph G:

    public static void main(String[] args) throws IOException {
//        Scanner in = new Scanner(new File("SCC.txt"));
    	
    	FileReader fr = new FileReader( "SCC2.txt" );
        BufferedReader br = new BufferedReader( fr );
        String line;
    	
        
        while ( ( line = br.readLine() ) != null )
        {
        	String[] s = line.trim().split(" ");
        	System.out.println("S[0] : " + s[0].trim());

            int startPoint = Integer.parseInt(s[0]);
            int endPoint = Integer.parseInt(s[1]);
            if (!adj.containsKey(startPoint)) adj.put(startPoint, new ArrayList<Integer>());
            adj.get(startPoint).add(endPoint);
            if (!revAdj.containsKey(endPoint)) revAdj.put(endPoint, new ArrayList<Integer>());
            revAdj.get(endPoint).add(startPoint);
        }
        br.close();
        fr.close();
        
        
        isExplored = new boolean[n+1];
        for (int i = n; i >= 1; i--)
            if (!isExplored[i]) dfs(revAdj, i, 0);
        isExplored = new boolean[n+1];
        for (int i = n; i >= 1; i--)
            if (!isExplored[markGraph[i]]) {countSCC = 0;
            dfs(adj, markGraph[i], 1);
            pushSCC(countSCC);
            }
        for (int i = 0; i <= 4; i++){
            if (i != 0) System.out.print(",");
            System.out.print(fiveLargestSCCs[i]);
        }
    }



The DFS function:

    static void dfs(Map<Integer,List<Integer>> graph, int currentPoint, int typeOfProcess){
        // typeOfProcess = 0: dfs on the reversed graph; typeOfProcess = 1: dfs on the original graph.
        isExplored[currentPoint] = true;
        if (typeOfProcess == 1) countSCC++;
        if (graph.containsKey(currentPoint)) {
            Iterator<Integer> endPointIt = graph.get(currentPoint).iterator();
            while (endPointIt.hasNext()) {
                int endPoint = endPointIt.next();
                if (!isExplored[endPoint]) dfs(graph, endPoint, typeOfProcess);
            }
        }
        if (typeOfProcess == 0){
            timer++;
            markGraph[timer] = currentPoint;
        }
    }


Update the array with SCC sizes:

    static void pushSCC(int scc){
        if (scc<=fiveLargestSCCs[4]) return;
        fiveLargestSCCs[4] = scc;
        for (int i = 3; i >= 0; i--)
            if (fiveLargestSCCs[i]<fiveLargestSCCs[i+1])
            {
                int t = fiveLargestSCCs[i+1];
                fiveLargestSCCs[i+1] = fiveLargestSCCs[i];
                fiveLargestSCCs[i] = t;
            }
    }


To repeat, the error occurred at the following line:

                if (!isExplored[endPoint]) dfs(graph, endPoint, typeOfProcess);





Any suggestions?! :surrender:

Is This A Good Question/Topic? 0
  • +

Replies To: Kosaraju's algorithm: Stackoverflow error

#2 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7744
  • View blog
  • Posts: 13,083
  • Joined: 19-March 11

Re: Kosaraju's algorithm: Stackoverflow error

Posted 04 June 2014 - 07:44 AM

Does this look familiar?

Quote

2. Sign the Coursera Honor Code

All students participating in the class must agree to abide by the following code of conduct:

  • I will register for only one account.
  • My answers to homework, quizzes and exams will be my own work (except for assignments that explicitly permit collaboration).
  • I will not make solutions to homework, quizzes or exams available to anyone else. This includes both solutions written by me, as well as any official solutions provided by the course staff.
  • I will not engage in any other activities that will dishonestly improve my results or dishonestly improve/hurt the results of others.


It should. It's the honor code you agreed to follow when you signed up for this course. You've violated two of the points here, and you're trying to violate a third. You really ought to consider what your self-respect is worth to you.
Was This Post Helpful? 0
  • +
  • -

#3 google_interview  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 49
  • Joined: 27-December 13

Re: Kosaraju's algorithm: Stackoverflow error

Posted 04 June 2014 - 10:37 AM

View Postjon.kiparsky, on 04 June 2014 - 07:44 AM, said:

Does this look familiar?

Quote

2. Sign the Coursera Honor Code

All students participating in the class must agree to abide by the following code of conduct:

  • I will register for only one account.
  • My answers to homework, quizzes and exams will be my own work (except for assignments that explicitly permit collaboration).
  • I will not make solutions to homework, quizzes or exams available to anyone else. This includes both solutions written by me, as well as any official solutions provided by the course staff.
  • I will not engage in any other activities that will dishonestly improve my results or dishonestly improve/hurt the results of others.


It should. It's the honor code you agreed to follow when you signed up for this course. You've violated two of the points here, and you're trying to violate a third. You really ought to consider what your self-respect is worth to you.



Thanks for reminding me, jon!
I am aware of it.

Yet - I have been struggling with this issue for the past 3 days and it's getting to me. Some small input would have been really helpful!
Sorry though.

This post has been edited by google_interview: 04 June 2014 - 10:38 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1