# Thread: Strongly connected components troubles

1. Member
Join Date
Nov 2011
Posts
9
Rep Power
0

## Strongly connected components troubles

Hi to everyone
I got a problem in my java code for finding strongly connected components in a directed graph (using adjacency list).
I'm trying to use Tarjan's algorithm but i'm finding really hard figuring out why i get these errors compiling the code.

at java.util.Stack.peek(Stack.java:85)
at Main.DepthFirstSearchRicorsivaEstesa(Main.java:41)
at Main.DepthFirstSearchRicorsivaEstesa(Main.java:39)
at Main.DepthFirstSearchRicorsivaEstesa(Main.java:39)
at Main.componentiFortementeConnesse(Main.java:24)
at Main.main(Main.java:148)'

Java Code:
```import java.util.*;
public class Tarjan{
static Vector<Vector<Integer>> nodiOut = new Vector<Vector<Integer>>();
static boolean[] completo=new boolean[6];
static  int[] dfsnumero=new int[6];
static int contatore=0;

static void componentiFortementeConnesse(Vector<Vector<Integer>> g){
for (int i=0;i<g.size();i++){
dfsnumero[i]=-1;
completo[i]=false;
}
for(int i=0;i<g.size();i++){
if(dfsnumero[i]==-1) DepthFirstSearchRicorsivaEstesa(i);
}
}
static void DepthFirstSearchRicorsivaEstesa(int u){
Stack<Integer> parziali=new Stack<Integer>();
Stack<Integer> rappresentanti=new Stack<Integer>();
dfsnumero[u]=contatore;
contatore++;
parziali.push(u);
rappresentanti.push(u);
for ( int x=0;x<nodiOut.get(u).size();x++){
int v =nodiOut.get(u).get(x);
if (dfsnumero[v]==-1){
DepthFirstSearchRicorsivaEstesa(v);
}else if(completo[v]==false){
while(dfsnumero[rappresentanti.peek()]>dfsnumero[v])
rappresentanti.pop();
}
}
if (u==rappresentanti.peek()){
System.out.println("Nuova componente fortemente connessa");
int z=parziali.pop();
System.out.println(z);
completo[z]=true;
while(z!=u){
rappresentanti.pop();
}
}
}

public static void main(String[] args) {

Vector<Integer> listazero=new Vector<Integer>();
Vector<Integer> listauno=new Vector<Integer>();

Vector<Integer> listatre=new Vector<Integer>();

Vector<Integer> listaquattro=new Vector<Integer>();
Vector<Integer> listacinque=new Vector<Integer>();

componentiFortementeConnesse(nodiOut);

}
}```

2. ## Re: Strongly connected components troubles

i get these errors compiling the code.
The error message you posted is from when you execute the code, not from when you compile the source.
at java.util.Stack.peek(Stack.java:85)
at Main.DepthFirstSearchRicorsivaEstesa(Main.java:41)
On line 41 you are calling the peek method and it is throwing the exception.
The error message says that the stack is empty.
You need to add code that tests if the stack is not empty before calling peek.
OR change your logic to not call peek when the stack is empty.

3. Member
Join Date
Nov 2011
Posts
9
Rep Power
0

## Re: Strongly connected components troubles

one error i've just found is that initialization of the two stack 'parziali' and 'rappresentanti' inside the recursive method.i have to declare them outside the method or they'll always be initializated as new every time

4. Member
Join Date
Nov 2011
Posts
9
Rep Power
0

## Re: Strongly connected components troubles

I've solved,the problem was in the last if of the depthsearch method
thanks anyway!

5. ## Re: Strongly connected components troubles

I knew you could do it. All you needed was a little push.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•