adjacency list creation , out of Memory error

Question

Hello ,

I am trying to create an adjacency list to store a graph.The implementation works fine while storing 100,000 records. However,when I tried to store around 1million records I ran into OutofMemory Error :

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.util.Arrays.copyOfRange(Arrays.java:3209) at java.lang.String.(String.java:215) at java.io.BufferedReader.readLine(BufferedReader.java:331) at java.io.BufferedReader.readLine(BufferedReader.java:362) at liarliar.main(liarliar.java:39)

Following is my implementation

HashMap<String,ArrayList<String>> adj = new HashMap<String,ArrayList<String>>(num);


        while ((str = in.readLine()) != null)
        {

            StringTokenizer Tok = new StringTokenizer(str);
            name = (String) Tok.nextElement();
            cnt = Integer.valueOf(Tok.nextToken());
            ArrayList<String> templist = new ArrayList<String>(cnt);

            while(cnt>0)
             {
                    templist.add(in.readLine());
                    cnt--;
             }
            adj.put(name,templist);

        } //done creating a adjacency list

I am wondering, if there is any better way to implement the adjacency list. Also, I know number of nodes right in the begining and , in the future I flatten the list as I visit nodes. Any suggestions ?

Thanks

Answer 1

I seem to have an unfair advantage here since I recognize both the name of the problem (liarliar) and the exact nature of the input.

I can tell you that this OutOfMemoryError is by design. You need to find a better algorithm that does not store the entire adjacency information of the graph in memory.

I will refrain from giving too much algorithmic insight, but I can tell you that you need to sit down and think more than you need to program at this stage. Maybe read a good book on algorithms and data structures.

---

What you're doing right now is that you're actually storing the strings from the input file unnecessarily into your HashMap<String,ArrayList<String>>. This is very space-inefficient given the nature of the problem.

It's much easier and much more efficient if you use a java.util.Scanner instead. new Scanner(new File(inputFilename)) and next(), and nextInt() are all that you need.

Assign a unique int to each name (hint: Map<String, Integer>), and store the much smaller int instead.

Answer 2

Hi polygenelubricants,

Thanks for answering my question. Yes you have guessed it right , what the code is about.

I think yes , using a mapping of string to integers would save me some space req for adjacency list. In that sense the above error can be removed.

However, I used java -jar -Xmx1024M. This gives a way to run the program with more heap memory , and since its allowed to use it in the given prolem , that shld not be the reason my submission is failing.

Performance can be one of the reason for failing the bot though I am not sure.

With regards to your solution,

If I create a Map ,and then store the numbers in the adjacencey list it would save me some space, but it will also add an extra lookup each time I need to access a node during my bfs/dfs traversal. That bothers me . Are you saying I should not create the adjacency list at all ? Did I understand what you are trying to say correctly.

thanks.