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)
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)