Results 1 to 5 of 5
  1. #1
    kilyx is offline Member
    Join Date
    Nov 2011
    Posts
    9
    Rep Power
    0

    Default 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.
    Thanks in advance to everyone

    'Exception in thread "main" java.util.EmptyStackException
    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>();
    		listazero.add(0,3);
    		listazero.add(1,1);
    		Vector<Integer> listauno=new Vector<Integer>();
    		listauno.add(0,5);
    		Vector<Integer> listadue=new Vector<Integer>();
    		listadue.add(0,0);
    
    		Vector<Integer> listatre=new Vector<Integer>();
    		listatre.add(0,2);
    
    		Vector<Integer> listaquattro=new Vector<Integer>();
    		listaquattro.add(0,1);
    		Vector<Integer> listacinque=new Vector<Integer>();
    		listacinque.add(0,4);
    
    
    
    		nodiOut.add(0,listazero);
    		nodiOut.add(1,listauno);
    		nodiOut.add(2,listadue);
    		nodiOut.add(3,listatre);
    		nodiOut.add(4,listaquattro);
    		nodiOut.add(5,listacinque);
    
    componentiFortementeConnesse(nodiOut);
    
    }
    }

  2. #2
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,559
    Rep Power
    25

    Default 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.
    'Exception in thread "main" java.util.EmptyStackException
    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. #3
    kilyx is offline Member
    Join Date
    Nov 2011
    Posts
    9
    Rep Power
    0

    Default 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. #4
    kilyx is offline Member
    Join Date
    Nov 2011
    Posts
    9
    Rep Power
    0

    Default Re: Strongly connected components troubles

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

  5. #5
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,559
    Rep Power
    25

    Default Re: Strongly connected components troubles

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

Similar Threads

  1. How to know if 3 machines in LAN are connected
    By Yogesh_P in forum Networking
    Replies: 1
    Last Post: 03-30-2011, 09:10 AM
  2. Replies: 5
    Last Post: 03-29-2011, 12:41 PM
  3. pc is connected to internet ???
    By mahdi-farzami in forum Networking
    Replies: 1
    Last Post: 03-26-2010, 03:28 PM
  4. JavaCard 3 (Connected edition) trouble
    By hendrix79 in forum Advanced Java
    Replies: 0
    Last Post: 11-19-2009, 11:20 PM
  5. Replies: 0
    Last Post: 06-11-2008, 11:10 AM

Posting Permissions

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