javadirected-acyclic-graphslongest-path

Unexpected Index out of bounds error for DAG


I'm writing a program to find the longest path for a DAG with input from standard in. I finally got it to compile, with it saying it is using unchecked or unsafe operations due to my Array list, but I am getting an index out of bounds error and it feels like I have tried changing every loop I must be missing something, thanks in advance for any tips.

Here is my code:

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

public class countLongPaths
{
    static final int NINF = Integer.MIN_VALUE;

    public class AdjListNode
    {
        private int v;
        private int weight;

        AdjListNode(int inV, int inW) 
        { 
          v = inV;  
          weight = inW; 
        }

        int getV() 
        { 
          return v; 
        }
        int getWeight()  
        { 
          return weight; 
        }
    }//end of adj list class
    
    public class Graph
    {
        private int V;
        private LinkedList<AdjListNode>adj[];
        
        //set up graph with given number of verticies
        Graph(int v)
        {
          V=v;
          adj = new LinkedList[V];
          for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList<AdjListNode>();
        }
        
        //function to add edges to graph
        void addEdge(int u, int v, int weight)
        {
          AdjListNode node = new AdjListNode(v,weight);
          adj[u].add(node);// Add v to u's list
        }
            
        //function to set order to go through vertices
        void setOrder(int v, Boolean visited[], Stack stack)
        {
          //Set node to visited when on it
          visited[v] = true;
          Integer i;
 
          //for all nodes connected to current repeat
          Iterator<AdjListNode> it = adj[v].iterator();
          while (it.hasNext())
          {
            AdjListNode node =it.next();
            if (!visited[node.getV()])
                 setOrder(node.getV(), visited, stack);
          }
      
          //Once done with current add it to the stack
          stack.push(new Integer(v));
        }

        //function to find longest paths from s
        int longestPath()
        {
           Stack stack = new Stack();
           int LP[] = new int[V];
           //set all vertices to unvisited
           Boolean visited[] = new Boolean[V];
           for(int i = 1; i <= V; i++)
             visited[i] = false;
             //call set order function from each vertex
             for (int i = 1; i <= V; i++)
             {
                if(visited[i] == false)
                setOrder(i, visited, stack);
             }
             //initialize distaces to all verices as negative infinity
             //set distace to source to 0
             LP[1] = 0;
             for(int i = 2; i <= V; i++)
                LP[i] = NINF;
             //go through vertices in order
             while(stack.empty() == false)
             { 
                int u = (int)stack.pop();
                //update LP for adj vertices
                Iterator<AdjListNode> it;
                if (LP[u] != NINF)
                {
                    it = adj[u].iterator();
                    while (it.hasNext())
                    {
                        AdjListNode i = it.next();
                        if(LP[i.getV()] < LP[u] + i.getWeight())
                            LP[i.getV()] = LP[u] + i.getWeight();
                    }
                }
            }
            return LP[V];               
        }
    }//end of graph class
        
    //Method to make a new graph
    public Graph newGraph(int number)
    {
       return new Graph(number);
    }
            
    public static void main(String[]args)
    {
        countLongPaths n = new countLongPaths();
        int GN = 0;
        int count = 1;
        Scanner scan = new Scanner(System.in);
        GN = scan.nextInt();
        while (count<= GN)
        {
            int N = 0;// nodes
            int M = 0;//edges
            
            N = scan.nextInt();
            M = scan.nextInt();
            
            //setup a new graph
            Graph g = n.newGraph(N);
            //set edges for new graph
            for(int i = 1; i <= M; i ++)
            {
                int I = scan.nextInt();
                int J = scan.nextInt();
                int W = scan.nextInt();
                g.addEdge(I, J, W);
            }
            int dist = 0;
            dist = g.longestPath();
            System.out.println("graph number: " + count);
            System.out.println("longest path: " + dist);
            System.out.println("number of longest paths: ");
            System.out.println();
            count++;
        }//end of while
            
    }//end main
}//end program

EDIT 1 with current code this is the error:

  Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
at countLongPaths$Graph.<init>(countLongPaths.java:36)
at countLongPaths.newGraph(countLongPaths.java:108)
at countLongPaths.main(countLongPaths.java:127)

Solution

  • As your stack trace says, the exception occurs in your Graph class constructor.

    More specifically it happens inside the only line in your loop:

    adj = new LinkedList[V];
    for (int i = 0; i <= v; ++i)
        adj[i] = new LinkedList<AdjListNode>();
    

    Assuming you've meant both lowercase v and uppercase V to be the same variable, you're defining an array of size V which is indexed from 0 to V-1, but you're running on it from 0 to V (your condition is i <= V), which is why you're getting an IndexOutOfBoundsException.

    Simply change the loop's condition (remove the =):

    for (int i = 0; i < v; ++i)