I'm trying to find all possible all possible paths in my graph. When I run the program I get an error saying ArrayIndexOutOfBoundsException. Where do I need to fix my code to resolve this error

private int v;  
 void printAllPaths(String s, String d) {
     int start=airportsHashMap.get(s).intValue();
        int end=airportsHashMap.get(d).intValue();

        //int DaRoute;
        printPaths(start,end);
 }
 public void printPaths(int s, int d)  
 { 

     boolean[] isVisited = new boolean[v]; 
     ArrayList<Integer> pathList = new ArrayList<>(); 

     //add source to path[] 
     pathList.add(s); 

     //Call recursive utility 
     printAllPathsUtil(s, d, isVisited, pathList); 
 } 

 // A recursive function to print 
 // all paths from 'u' to 'd'. 
 // isVisited[] keeps track of 
 // vertices in current path. 
 // localPathList<> stores actual 
 // vertices in the current path 
 private void printAllPathsUtil(Integer u, Integer d, 
                                 boolean[] isVisited, 
                         List<Integer> localPathList) { 

     // Mark the current node 
     isVisited[u] = true; 

     if (u.equals(d))  
     { 
         System.out.println(localPathList); 
         // if match found then no need to traverse more till depth 
         isVisited[u]= false; 
         return ; 
     } 

     // Recur for all the vertices 
     // adjacent to current vertex 
     for (Integer i :adjListArray[u])  
     { 
         if (!isVisited[i]) 
         { 
             // store current node  
             // in path[] 
             localPathList.add(i); 
             printAllPathsUtil(i, d, isVisited, localPathList); 

             // remove current node 
             // in path[] 
             localPathList.remove(i); 
         } 
     } 

     // Mark the current node 
     isVisited[u] = false; 
 } 

I expected the output to look like:

All paths between EWR and PHL

EWR IAD ILG PHL EWR IAD PHL EWR PHL

All paths betwee EWR and ILG

EWR IAD ILG EWR IAD PHL ILG EWR PHL ILG EWR PHL IAD ILG

1 Answers

0
Navy Cheng On

I think the Exception is because your misuse of remove. You should pass an index instead of 'object'.

 for (Integer i :adjListArray[u])  
 { 
     if (!isVisited[i]) 
     { 
         // store current node  
         // in path[] 
         localPathList.add(i);                 <=== i the 'object'
         printAllPathsUtil(i, d, isVisited, localPathList); 

         // remove current node 
         // in path[] 
         localPathList.remove(i);              <=== i should be 'index' not object
     } 
 } 

Your cold sholud like this:

 for (Integer i :adjListArray[u])  
 { 
     if (!isVisited[i]) 
     { 
         // store current node  
         // in path[] 
         localPathList.add(i);
         printAllPathsUtil(i, d, isVisited, localPathList); 

         // remove current node 
         // in path[] 
         localPathList.remove(localPathList.size()-1);
     } 
 }