Stack overflow error for large inputs in Java

Question

I'm writing a Java program that searches for and outputs cycles in a graph. I am using an adjacency list for storing my graph, with the lists stored as LinkedLists. My program takes an input formatted with the first line as the number of nodes in the graph and each subsequent line 2 nodes that form an edge e.g.:

3
1 2
2 3
3 1

My problem is that when the inputs get very large (the large graph I am using has 10k nodes and I don't know how many edges, the file is 23mb of just edges) I am getting a java.lang.StackOverflowError, but I don't get any errors with small inputs. I'm wondering if it would be better to use another data structure to form my adjacency lists or if there is some method I could use to avoid this error, as I'd rather not just have to change a setting on my local installation of Java (because I have to be sure this will run on other computers that I can't control the settings on as much). Below is my code, the Vertex class and then my main class. Thanks for any help you can give!

Vertex.java:

package algorithms311;

import java.util.*;

public class Vertex implements Comparable {

    public int id;
    public LinkedList adjVert = new LinkedList();
    public String color = "white";
    public int dTime;
    public int fTime;
    public int prev;

    public Vertex(int idnum) {
        id = idnum;
    }

    public int getId() {
        return id;
    }

    public int compareTo(Object obj) {
        Vertex vert = (Vertex) obj;
        return id-vert.getId();
    }

    @Override public String toString(){
        return "Vertex # " + id;
    }

    public void setColor(String newColor) {
        color = newColor;
    }

    public String getColor() {
        return color;
    }

    public void setDTime(int d) {
        dTime = d;
    }

    public void setFTime(int f) {
        fTime = f;
    }

    public int getDTime() {
        return dTime;
    }

    public int getFTime() {
        return fTime;
    }

    public void setPrev(int v) {
        prev = v;
    }

    public int getPrev() {
        return prev;
    }

    public LinkedList getAdjList() {
        return adjVert;
    }

    public void addAdj(int a) { //adds a vertex id to this vertex's adj list
        adjVert.add(a);
    }
}

CS311.java:

package algorithms311;

import java.util.*;
import java.io.*;

public class CS311 {

    public static final String GRAPH= "largegraph1";

    public static int time = 0;


    public static LinkedList[] DFS(Vertex[] v) {

        LinkedList[] l = new LinkedList[2];
        l[0] = new LinkedList();
        l[1] = new LinkedList(); //initialize the array with blank lists, otherwise we get a nullpointerexception

        for(int i = 0; i < v.length; i++) {
            v[i].setColor("white");
            v[i].setPrev(-1);
        }
        time = 0;
        for(int i = 0; i < v.length; i++) {
            if(v[i].getColor().equals("white")) {
                l = DFSVisit(v, i, l);
            }
        }
        return l;
    }

    public static LinkedList[] DFSVisit(Vertex[] v, int i, LinkedList[] l) { //params are a vertex of nodes and the node id you want to DFS from

        LinkedList[] VOandBE = new LinkedList[2]; //two lists: visit orders and back edges

        VOandBE[0] = l[0]; // l[0] is visit Order, a linked list of ints

        VOandBE[1] = l[1]; // l[1] is back Edges, a linked list of arrays[2] of ints

        VOandBE[0].add(v[i].getId());

        v[i].setColor("gray");  //color[vertex i] <- GRAY
        time++;                 //time <- time+1
        v[i].setDTime(time);    //d[vertex i] <- time

        LinkedList adjList = v[i].getAdjList(); // adjList for the current vertex

        for(int j = 0; j < adjList.size(); j++) {   //for each v in adj[vertex i]

            if(v[(Integer)adjList.get(j)].getColor().equals("gray") && v[i].getPrev() != v[(Integer)adjList.get(j)].getId()) { //  if color[v] = gray and Predecessor[u] != v do
                int[] edge = new int[2]; //pair of vertices
                edge[0] = i; //from u
                edge[1] = (Integer)adjList.get(j); //to v
                VOandBE[1].add(edge);
            }
            if(v[(Integer)adjList.get(j)].getColor().equals("white")) { //do if color[v] = WHITE
                v[(Integer)adjList.get(j)].setPrev(i);  //then "pi"[v] <- vertex i
                DFSVisit(v, (Integer)adjList.get(j), VOandBE);   //DFS-Visit(v)
            }
        }

        VOandBE[0].add(v[i].getId());

        v[i].setColor("black");
        time++;
        v[i].setFTime(time);

        return VOandBE;
    }


    public static void main(String[] args) {
        try {

            // --Read First Line of Input File
            // --Find Number of Vertices

            FileReader file1 = new FileReader("W:\\Documents\\NetBeansProjects\\algorithms311\\src\\algorithms311\\" + GRAPH);
            BufferedReader bReaderNumEdges = new BufferedReader(file1);

            String numVertS = bReaderNumEdges.readLine();
            int numVert = Integer.parseInt(numVertS);

            System.out.println(numVert + " vertices");





            // --Make Vertices

            Vertex vertex[] = new Vertex[numVert];

            for(int k = 0; k <= numVert - 1; k++) {
                vertex[k] = new Vertex(k);
            }

            // --Adj Lists


            FileReader file2 = new FileReader("W:\\Documents\\NetBeansProjects\\algorithms311\\src\\algorithms311\\" + GRAPH);
            BufferedReader bReaderEdges = new BufferedReader(file2);
            bReaderEdges.readLine(); //skip first line, that's how many vertices there are

            String edge;

            while((edge = bReaderEdges.readLine()) != null) {

                StringTokenizer ST = new StringTokenizer(edge);

                int vArr[] = new int[2];
                for(int j = 0; ST.hasMoreTokens(); j++) {
                    vArr[j] = Integer.parseInt(ST.nextToken());
                }


                vertex[vArr[0]-1].addAdj(vArr[1]-1);
                vertex[vArr[1]-1].addAdj(vArr[0]-1);

            }

            for(int i = 0; i < vertex.length; i++) {
                System.out.println(vertex[i] + ", adj nodes: " + vertex[i].getAdjList());
            }

            LinkedList[] l = new LinkedList[2];
            l = DFS(vertex);

            System.out.println("");
            System.out.println("Visited Nodes: " + l[0]);
            System.out.println("");
            System.out.print("Back Edges: ");

            for(int i = 0; i < l[1].size(); i++) {
                int[] q = (int[])(l[1].get(i));
                System.out.println("[" + q[0] + "," + q[1] + "] ");
            }

            for(int i = 0; i < l[1].size(); i++) { //iterate through the list of back edges
                int[] q = (int[])(l[1].get(i)); // q = pair of vertices that make up a back edge
                int u = q[0]; // edge (u,v)
                int v = q[1];

                LinkedList cycle = new LinkedList();

                if(l[0].indexOf(u) < l[0].indexOf(v)) { //check if u is before v
                    for(int z = l[0].indexOf(u); z <= l[0].indexOf(v); z++) { //if it is, look for u first; from u to v
                        cycle.add(l[0].get(z));
                    }
                }
                else if(l[0].indexOf(v) < l[0].indexOf(u)) {
                    for(int z = l[0].indexOf(v); z <= l[0].indexOf(u); z++) { //if it is, look for u first; from u to v
                        cycle.add(l[0].get(z));
                    }
                }

                System.out.println("");
                System.out.println("Cycle detected! : " + cycle);
                if((cycle.size() & 1) != 0) {
                    System.out.println("Cycle is odd, graph is not 2-colorable!");
                }
                else {
                    System.out.println("Cycle is even, we're okay!");
                }
            }

        }

        catch (IOException e) {
            System.out.println("AHHHH");
            e.printStackTrace();
        }
    }
}

Answer 1

The stack is a region in memory that is used for storing execution context and passing parameters. Every time your code invokes a method, a little bit of stack is used, and the stack pointer is increased to point to the next available location. When the method returns, the stack pointer is decreased and the portion of the stack is freed up.

If an application uses recursion heavily, the stack quickly becomes a bottleneck, because if there is no limit to the recursion depth, there is no limit to the amount of stack needed. So you have two options: increase the Java stack (-Xss JVM parameter, and this will only help until you hit the new limit) or change your algorithm so that the recursion depth is not as deep.

I am not sure if you were looking for a generic answer, but from a brief glance at your code it appears that your problem is recursion.

Answer 2

The issue is most likely the recursive calls in DFSVisit. If you don't want to go with the 'easy' answer of increasing Java's stack size when you call the JVM, you may want to consider rewriting DFSVisit to use an iterative algorithm instead of recursive. While Depth First Search is more easily defined in a recursive manner, there are iterative approaches to the algorithm that can be used.

For example: this blog post

Answer 3

If you're sure your algorithm is correct and the depth of recursive calls you're making isn't accidental, then solutions without changing your algorithm are:

• add to the JVM command line e.g. -Xss128m to set a 128 MB stack size (not a good solution in multi-threaded programs as it sets the default stack size for every thread not just the particular thread running your task);
• run your task in its own thread, which you can initialise with a stack size specific to just that thread (and set the stack size within the program itself)-- see my example in the discussion of fixing StackOverflowError, but essentially the stack size is a parameter to the Thread() constructor;
• don't use recursive calls at all-- instead, mimic the recursive calls using an explicit Stack or Queue object (this arguably gives you a bit more control).