How come I cannot (for) loop the input for my Graph's nodes and edges?

Question

This is my code:

import java.util.*;

public class Dijkstra {

// 1 = A
// 2 = B
// 3 = C
// 4 = D
// 5 = E
// 6 = F
// 7 = G
// 8 = H

private static final Graph.Edge[] GRAPH = null;

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Graph.Edge[] GRAPH = { 
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt())
            };

    String START = sc.next();
    String END = sc.next();
    Graph g = new Graph(GRAPH);
    g.dijkstra(START);
    // print the shortest path using Dijkstra algorithm
    g.printPath(END);
    // g.printAllPaths();
    }
}

class Graph {
    public static Map<String, Vertex> graph; // mapping of vertex names to 
Vertex objects, built from a set of Edges

/** One edge of the graph (only used by Graph constructor) */
public static class Edge {
    public String v1, v2;
    public int dist;

    public Edge(String v1, String v2, int dist) {
        this.v1 = v1;
        this.v2 = v2;
        this.dist = dist;
    }
}

/** One vertex of the graph, complete with mappings to neighbouring vertices */
public static class Vertex implements Comparable<Vertex> {
    public String name;
    public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
    public Vertex previous = null;
    public Map<Vertex, Integer> neighbours = new HashMap<Vertex, Integer>();

    public Vertex(String name) {
        this.name = name;
    }

    public void printPath() {
        if (this == this.previous) {
            System.out.println(this.name);
        } else if (this.previous == null) {
            System.out.printf("%s(unreached)", this.name);
        } else {
            this.previous.printPath();
            System.out.println(this.name);
        }
    }

    public int compareTo(Vertex other) {
        if (dist == other.dist)
            return name.compareTo(other.name);
        return Integer.compare(dist, other.dist);
    }
}

/** Builds a graph from a set of edges */
public Graph(Edge[] edges) {
    graph = new HashMap<String, Vertex>(edges.length);

    // one pass to find all vertices
    for (Edge e : edges) {
        if (!graph.containsKey(e.v1))
            graph.put(e.v1, new Vertex(e.v1));
        if (!graph.containsKey(e.v2))
            graph.put(e.v2, new Vertex(e.v2));
    }

    // another pass to set neighbouring vertices
    for (Edge e : edges) {
        graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
        graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph
    }
}

/** Runs dijkstra using a specified source vertex */
public void dijkstra(String startName) {
    if (!graph.containsKey(startName)) {
        System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
        return;
    }
    final Vertex source = graph.get(startName);
    NavigableSet<Vertex> q = new TreeSet<Vertex>();

    // set-up vertices
    for (Vertex v : graph.values()) {
        v.previous = v == source ? source : null;
        v.dist = v == source ? 0 : Integer.MAX_VALUE;
        q.add(v);
    }

    dijkstra(q);
}

/** Implementation of dijkstra's algorithm using a binary heap. */
private void dijkstra(final NavigableSet<Vertex> q) {
    Vertex u, v;
    while (!q.isEmpty()) {

        u = q.pollFirst(); // vertex with shortest distance (first iteration will return source)
        if (u.dist == Integer.MAX_VALUE)
            break; // we can ignore u (and any other remaining vertices) since they are unreachable

        // look at distances to each neighbour
        for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
            v = a.getKey(); // the neighbour in this iteration

            final int alternateDist = u.dist + a.getValue();
            if (alternateDist < v.dist) { // shorter path to neighbour found
                q.remove(v);
                v.dist = alternateDist;
                v.previous = u;
                q.add(v);
            }
        }
    }
}

/** Prints a path from the source to the specified vertex */
public void printPath(String endName) {
    if (!graph.containsKey(endName)) {
        System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
        return;
    }

    graph.get(endName).printPath();
}

/**
 * Prints the path from the source to every vertex (output order is not
 * guaranteed)
 */
public void printAllPaths() {
    for (Vertex v : graph.values()) {
        v.printPath();
        }
    }
}

In my main method, I am trying to loop the input for the graph:

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Graph.Edge[] GRAPH = { 
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt())
                };

        String START = sc.next();
        String END = sc.next();
        Graph g = new Graph(GRAPH);
        g.dijkstra(START);
        // print the shortest path using Dijkstra algorithm
        g.printPath(END);
        // g.printAllPaths();
    }

So I'm trying to make it loop like this, where I can loop the graph input n times. However, whenever I do this, there is an issue

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    for(int i = 0; i < n; i++) {
        Graph.Edge[] GRAPH = {
            new Graph.Edge(sc.next(),sc.next(),sc.nextInt())
        };
    }

The error is:

Exception in thread "main" java.lang.NullPointerException
at Graph.<init>(Dijkstra.java:80)
at Dijkstra.main(Dijkstra.java:26)

I would like to know what the issue is, but as well as a solution to the problem.

You should read about [debugging](https://www.google.de/search?q=java+debugging) — leonardkraemer, Apr 06 '18 at 00:13
Possible duplicate of [What is a NullPointerException, and how do I fix it?](https://stackoverflow.com/questions/218384/what-is-a-nullpointerexception-and-how-do-i-fix-it) — leonardkraemer, Apr 06 '18 at 00:14
Interesting how simply creating a loop can cause a NullPointerException — TimothyW553, Apr 06 '18 at 00:41
Definitely. Get used to it. And I dont mean that in a bad way. — leonardkraemer, Apr 06 '18 at 00:42

tommybee · Accepted Answer · 2018-04-06T03:51:02.453

I found that there was no problem as I tested your code a while using two cases, built from static data and from console input.

Here is my methods of the cases as follows:

private static final Graph.Edge[] buildData()
{
    Graph.Edge[] GRAPH = { 
        new Graph.Edge("A", "B", 5),
        new Graph.Edge("C", "D", 7), 
        new Graph.Edge("E", "F", 3),
        new Graph.Edge("G", "H", 2), 
        new Graph.Edge("B", "C", 1),
        new Graph.Edge("D", "E", 9), 
        new Graph.Edge("A", "H", 4),
        new Graph.Edge("G", "B", 6) 
    };

    return GRAPH;
}

and two methods.

public static void main_build(String[] args) {
    String START = "A";
    String END = "G";
    Graph.Edge[] GRAPH = buildData();
    Graph g = new Graph(GRAPH);

    g.dijkstra(START);
    // print the shortest path using Dijkstra algorithm
    g.printPath(END);
    //g.printAllPaths();
}

public static void main_input(String[] args) {
    Scanner sc = new Scanner(System.in);
    //int n = sc.nextInt();
    //
    Graph.Edge[] GRAPH = { 
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()), 
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()), 
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()), 
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()) 
    };

    String START = sc.next();
    String END = sc.next();
    Graph g = new Graph(GRAPH);

    g.dijkstra(START);
    // print the shortest path using Dijkstra algorithm
    g.printPath(END);
    // g.printAllPaths();

    sc.close();
    sc = null;
}

The key input for the second method, main_input must be,

A B 5 C D 7 E F 3 G H 2 B C 1 D E 9 A H 4 G B 6 A G

About for loop statement, it's the same way as the method i described before.

Here is a for loop method, your for loop statement looks like;

public static void main_forloop(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Graph.Edge[] GRAPH = new Graph.Edge[n];

    for(int i = 0; i < n; i++) {
        GRAPH[i] = 
            new Graph.Edge(sc.next(),sc.next(),sc.nextInt());
    }

    String START = sc.next();
    String END = sc.next();
    Graph g = new Graph(GRAPH);

    g.dijkstra(START);
    // print the shortest path using Dijkstra algorithm
    g.printPath(END);
    // g.printAllPaths();

    sc.close();
    sc = null;
}

The console input is:

8 A B 5 C D 7 E F 3 G H 2 B C 1 D E 9 A H 4 G B 6 A G

You can compare the out with following console output image with yours in eclipse environment.

There are so many articles about dijkstra algorithms. I think it's not a program issue but a test data.

I found this site with test data files.

Shortest Paths

You can test your code with the data from the site - you need to build data from the files using file stream classes in java.

I hope this can help you.

Were you able to loop `new Graph.Edge(sc.next(), sc.next(), sc.nextInt()) ` with a for loop instead of creating many instances of the same line? — TimothyW553, Apr 06 '18 at 03:08
I added a for-loop statement of mine. compare the result and code with yours. — tommybee, Apr 06 '18 at 03:52

How come I cannot (for) loop the input for my Graph's nodes and edges?

1 Answers1