up vote 0 down vote favorite 
void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack, ArrayList<Integer>[] adj) {
        visited[v] = true;
        for (int i : adj[v]) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, stack, adj);
            }
        }

        stack.push(v);
    }

Here, I am calling an array of arraylist. The error is in the enhanced for loop, as told by my IDE (IntelliJ). It seems like a perfectly valid call as adj[v] would return an ArrayList and the integer i catching each elements of the array as they come and then processing them in the recursive call.

@Alex Shesterov and others, Here is the code using which adj was generated.

    ArrayList[] arr = new ArrayList[n+1];
        for(int i=0; i<=n; i++){
            arr[i] = new ArrayList<Integer>();
        }
        arr[1].add(Arrays.asList(8,6,2));
        arr[2].add(Arrays.asList(7));
        arr[3].add(Arrays.asList(6));
        arr[4].add(Arrays.asList(5,2));
        arr[5].add(Arrays.asList(4,2,3));
        arr[6].add(Arrays.asList(3,2,5));
        arr[7].add(Arrays.asList(2));
        arr[7].add(Arrays.asList(1,2,4));
share
1  
adj is an array of ArrayList<Integer> type and in your foreach loop int i cannot hold an arraylist – Pavneet_Singh Oct 31 '16 at 14:16
    
Are you sure the error is in that code? It seems to be somewhere where you use the Arrays class. – RealSkeptic Oct 31 '16 at 14:22
up vote 0 down vote accepted

The code in which you generate the array is incorrect and type-unsafe. You are probably getting warnings about "unsafe types" or "raw types" from the compiler. The following is a use of a raw type:

ArrayList[] arr = new ArrayList[n+1];

You should never use the type ArrayList without some kind of type declaration.

You then initialize each of the elements of arr to be an ArrayList<Integer>. But since this is assigned to a raw typed array element, the compiler doesn't know that the element is an ArrayList<Integer> and doesn't warn you about your next step, which is the bad one:

arr[1].add(Arrays.asList(8,6,2));

You add an element to the list in arr[1]. The add method adds a single element, which is the object that is passed to it. And what is that object? It's a List, which is produced by Arrays.asList(...).

So instead of having an ArrayList<Integer> you have a raw ArrayList which has a single element, and that element is a list of integer. And this, of course, cannot be cast to Integer.

Instead of using add you should have used addAll. The addAll method adds all the elements in the collection it receives to the collection on which it is called.

arr[1].addAll(Arrays.asList(8,6,2));

It would have been better not to mix arrays and lists, but to pass a list of lists and give it the appropriate type.

Try to avoid raw types and eliminate all raw type or unsafe type warnings from your code (not by @SupressWarnings!), unless you start programming libraries for generic collections and you know what you are doing.

share
    
Very detailed answer. I used addAll before you answered and it worked. But didn't really know 'why'. Thanks a lot! – MightyPhoenix17 Nov 1 '16 at 18:59
up vote 0 down vote

Error is in method call.Probably when you are calling topologicalSortUtil first time. You are passing integer instead of list of integer

Incorrect Method Call

topologicalSortUtil(1,booleanArray,passingIntegerInsteadOfList,stack)

ImplementedMethod

void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack, 
    }
share
    
This is a bit cryptic. The method is recursive, it calls itself. Its parameters are int, boolean [], Stack<Integer> and ArrayList<Integer>[] and these are also the arguments in the call. So not sure what you are trying to say here. – RealSkeptic Oct 31 '16 at 14:25
    
@RealSkeptic i understand topologicalSortUtil is recursive. But looks like error is in code which call topologicalSortUtil first time. For example topologicalSortUtil first call may be from main method and then it will be recursive – M Sach Oct 31 '16 at 14:28
    
I would re-write the answer if that is the case. It's not clear where you deduced that the user is actually calling the "Incorrect method call", and the "Implemented method" is not even syntactically correct. Just explain without adding code that doesn't exist. – RealSkeptic Oct 31 '16 at 14:30
    
It's not clear where you deduced that the user is actually .. to me it seems that is the only possibility based on code posted – M Sach Oct 31 '16 at 14:33
    
Actually, look at Alex Shesterov's answer. It makes much more sense. Also, if the user tried to call the method with an integer instead of a list, he would get a compile error, not a runtime exception. And please read your two pieces of code carefully. Do you really believe they make sense? – RealSkeptic Oct 31 '16 at 15:10
up vote 0 down vote

The exception suggests that the adj array, which is supposed to contain instances of ArrayList<Integer>, actually contains an ArrayList which has a java.util.Arrays$ArrayList as an element.

Thus, the enhanced loop runs into a ClassCastException when it hits such an element of the ArrayList and tries to "interpret" it as an Integer.

Please inspect and/or post the code which builds the adj array.

Also, please look for the "Type safety" and "Raw types" warnings in your code — you may have unsafely ignored a couple of them which led to this exception.

Update:

As expected, the problem is that you are adding lists as elements of the lists which are elements of the adj/arr array. E.g. the following lines: 

ArrayList[] arr = new ArrayList[n+1];
arr[1] = new ArrayList<Integer>();
arr[1].add(Arrays.asList(8,6,2));

would result in the following structure: 

arr - array
  [0] : ...
  [1] : ArrayList (of lists) :
          [0] : List (of integers) : 
                  [0] : 8
                  [1] : 6
                  [2] : 2
  [2] : ...
  ...

List.add() adds a single element to the list.

What you need is the List.addAll() method, which adds all elements from a collection (and not the collection itself) into the list: 

arr[1].addAll(Arrays.asList(8,6,2));

This would have produced the following structure: 

arr - array
  [0] : ...
  [1] : ArrayList (of integers) :
          [0] : 8
          [1] : 6
          [2] : 2
  [2] : ...
  ...

Another note: you should never use raw generic types — using explicit generic arguments would have produced a compile-time error for your code above, and the problem would have been very easy to find and fix.

share
    
please look into the code I pasted now. This part generates the adj. – MightyPhoenix17 Oct 31 '16 at 17:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.