Java - NullPointerException in Graph.java

Question

I am trying to create an undirected graph that is read from a text file. However I keep getting a NullPointerException. This is my Graph class:

Graph.java:

    package testalgo;

    import java.io.File;
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Scanner;


    public class Graph

    {   


            ArrayList<Integer> vertices = new ArrayList<Integer>();
           HashMap<Integer, LinkedList<Integer>> adj;
           static Scanner sc;
            public Graph(ArrayList<Integer> verts ){

                   adj =new HashMap<Integer, LinkedList<Integer>>();
            }

            public static void main(String[] args) {

                try{
                sc = new Scanner(new File("graph1.txt"));
                }
                catch(Exception e){

                    System.out.println(e);
                }

                while(sc.hasNext()){

                    int a = Integer.parseInt(sc.next());
                    int b = Integer.parseInt(sc.next());
                    Graph g = new Graph(new ArrayList<Integer>());
                    g.addVertex(a);
                    g.addeEgde(a, b); // this is line 46
                    g.addeEgde(b, a);


                }

                 sc.close();
            }

            public void addVertex(int v){


                for (int i = 1; i < vertices.size(); ++i) {
                adj.put(i, new LinkedList<Integer>());}

            }

            public  void addeEgde(int v1, int v2) {

                adj.get(v1).add(v2); // this is line 68
            }

            public List<Integer> getNeighbors(int v) {
                return adj.get(v);
         }
  }

And this is the error message that I am getting:

Exception in thread "main" java.lang.NullPointerException
    at testalgo.Graph.addeEgde(Graph.java:68)
    at testalgo.Graph.main(Graph.java:46)

Thank you for all your help!

As a side note: When I read something thats a Map of a List of a ....I think, perhaps its time to introduce some new abstractions — Amir Afghani
– Amir Afghani, Commented Mar 16, 2015 at 16:48

Vivin Paliath · Accepted Answer · 2015-03-16 17:15:14Z

3

I don't see anywhere in your code where you're populating the the adj map with v as a key. Hence adj.get(v1) will return null. You've only declared adj; you need to populate it as well.

All I see is:

for (int i = 1; i < vertices.size(); ++i) {
    adj.put(i, new LinkedList<Integer>());
}

Since vertices is empty to begin with, you won't be inserting anything into your map.

Did you mean:

adj.put(v, new LinkedList<Integer>());

instead?

In response to your comment: you need to add another entry for b in your adjacency list:

g.addVertex(a);
g.addVertex(b); // <--- you need this as well
g.addeEgde(a, b);
g.addeEgde(b, a); // <--- otherwise you'll get a NPE here

edited Mar 16, 2015 at 17:15

answered Mar 16, 2015 at 16:44

Vivin Paliath

95.8k42 gold badges230 silver badges302 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

new_to_coding Over a year ago

I have changed it and the error still comes up.Any ideas ? Thanks!

Vivin Paliath Over a year ago

Did you also add an entry for b in your adjacency list?

Nick Louloudakis · Accepted Answer · 2015-03-16 17:35:54Z

1

You probably have invoked addeEdge without having added any vertex, as

for (int i = 1; i < vertices.size(); ++i)
{
  adj.put(i, new LinkedList<Integer>());
}

Will not put any LinkedList instance in adj (vertices.size() is 0).

Therefore,

adj.get(v1).add(v2);

Will throw a NullPointerException, as adj.get(v1) will return null and you are invoking add on null.

Try declaring:

private static int count = 0;

In class body, and then, in addVertex:

adj.put(count++, new LinkedList<Integer>());

This one will put a new LinkedList in your Map every time addVertex is invoked.

Alternatively, for the map index:

public void addVertex(int vertexIndex)
{
  adj.put(vertexIndex, new LinkedList<Integer>());
}

In addition, ensure that adj.get(v1) will not be null by making a null check comparison before calling add on it:

LinkedList<Integer> vertex = adj.get(v1);
if(vertex != null)
{
  vertex.add(v2);
}

Also, cosider that g.addeEgde(b, a); applies to a vertex that does not exist and will be a source of NullPointerException too.

UPDATE: In the case you are attempting to insert values in a sequence (sequential index), using a Map for your vertexes is not the mostly efficient way of doing this (takes O(logn) complexity time of indexing). I suggest that you use an ArrayList instead:

ArrayList<LinkedList<Integer>> adj;

And in your addVertex:

adj.add(new LinkedList<Integer>());

And when indexing:

adj.get(yourIndex);

This one will be much more efficient (takes O(1) complexity time in indexing).

UPDATE 2: If your case is an adjacency list, which probably is, the Map is better to use than the ArrayList, as you do not have a sequential indexing. Take in mind you must add vertices by adjacency value and NOT sequential indexing, as Vivin Paliath mentioned.

edited Mar 16, 2015 at 17:35

answered Mar 16, 2015 at 16:48

Nick Louloudakis

6,0254 gold badges43 silver badges57 bronze badges

10 Comments

new_to_coding Over a year ago

Thanks for your answer ! When i try adj.put(new LinkedList<Integer>()); I get an error.

Vivin Paliath Over a year ago

adj.put(new LinkedList<Integer>()); will result in a compile-time error. Map#put requires two arguments.

Vivin Paliath Over a year ago

adj is an adjacency list. He shouldn't be setting the keys based on the number of vertices thus far; it should be done based on the value of the graph node.

Nick Louloudakis Over a year ago

Answer Updated again. I suggest the use of ArrayList as a Map will not be the most efficient in numeric indexing.

Vivin Paliath Over a year ago

Again, your solution won't result in a proper graph-implementation. The function of an adjacency list is to maintain a list of nodes adjacent to a given node (i.e., nodes that are reachable from a vertex node). With your current implementation, how would it be possible to look up the adjacency list for a node by the value of that node? What if the first value that comes in is 10? It won't get an entry in the adjacency list, and its neighbors won't be added in either since you perform the null check to see if an entry even exists.

|

gilleain · Accepted Answer · 2015-03-16 17:18:02Z

0

This is more of a code review comment, but :

Formatting - your IDE can do this (assuming you are using one..).
Use List rather than ArrayList, and Map rather than Hashmap, so HashMap<Integer, LinkedList<Integer>> adj; becomes Map<Integer, List<Integer>>
The method name addeEgde - c'mon!
You don't actually use the ArrayList<Integer> that you pass to the constructor of Graph - do you really need it?

From experience of implementing (far too many) graph objects, you might want to consider how you would make one that could use a fixed int matrix instead of the adjacency list approach. Both implementations can be useful, but in different circumstances.

answered Mar 16, 2015 at 17:18

gilleain

6513 gold badges11 silver badges25 bronze badges

Collectives™ on Stack Overflow

Java - NullPointerException in Graph.java

3 Answers 3

2 Comments

10 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

10 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related