Skip to content
Advertisement

Array out of bound exception while doing topological sort

This code takes the no. of nodes in a graph and creates the graph with the number of nodes and then the user has to input the one-way edges between two vertices.(The formed Graph is a Directed Acyclic Graph or DAG). The graph is then sorted by the topological sorting function topoSort The problem is in the topoSortRE method which is a recursive method that gets called in topoSort which checks whether the vertices are visited or not but in my run with the following input:

5(no. of nodes) 7(no. of edges)

the connections of edges: 1-2, 1-3, 1-4, 1-5, 2-4, 2-5, 3-4,

the boolean array visited is out of bounds

public class n {
    public static void main(String[] args) throws Bounds{
        Scanner sc= new Scanner (System.in);
        System.out.println("Enter no. of Islands");
        int n= sc.nextInt();
        Graph g = new Graph (n);
        System.out.println("Enter no. of one-way bridges");
        int m= sc.nextInt();
        try { 
            for (int i=0; i<m;i++){ 
                System.out.println("This one-way bridge connects between");
                int u = sc.nextInt();
                int v = sc.nextInt();
                if(u == v){ throw new Bounds("");}
                else{ g.addEdge(u, v);}
            }
        } catch(IndexOutOfBoundsException e){
            System.out.println("Please enter a valid input!");
        } catch(Bounds e){
            System.out.println("Please enter a valid input!");
        }
        g.topoSort();  
    }

    public static class Bounds extends Exception {
        public Bounds (String message){
            super(message);
        }
    }   

    public static class Graph  {  
        private int V;    
        private ArrayList<ArrayList<Integer>> adj;  

        Graph(int v) {  
            V = v;  
            adj = new ArrayList<ArrayList<Integer>>(v);  
            for (int i=0; i<v; ++i)  
                adj.add(new ArrayList<Integer>());  
        }  

        void addEdge(int v,int w) { adj.get(v).add(w); }  

        void topoSortRE( int v, boolean visited[], Stack<Integer> stack) {  
            visited[v] = true;  
            Integer i;  

            Iterator<Integer> it = adj.get(v).iterator();  
            while (it.hasNext()) {  
                i = it.next();  
                if (false == visited[i])  
                    topoSortRE(i, visited, stack);  
            }  
            stack.push(new Integer(v));  
        }

        void topoSort() {  
            Stack<Integer> stack = new Stack<>();  

            boolean visited[] = new boolean[V];  
            for (int i = 0; i < V; i++)  
                visited[i] = false;  

            for (int i = 0; i < V; i++)  
                if (visited[i] == false)  
                    topoSortRE(i, visited, stack);  

            while (stack.isEmpty()==false)  
                System.out.print(stack.pop() + " ");  
        } 
    }
}

Advertisement

Answer

Looks like you are trying to use island numbers as array indices. Setting a bridge between islands 1-5 means setting a bridge between island with indices 0-4. 

void topoSortRE( int v, boolean visited[], Stack<Integer> stack) {
    visited[v] = true;
    Integer i;

    Iterator<Integer> it = adj.get(v).iterator();
    while (it.hasNext()) {
        i = it.next() - 1; // -1 to make bridge number to be bridge index in array
        if (false == visited[i])
            topoSortRE(i, visited, stack);
    }
    stack.push(new Integer(v));
}

You definitely need to get yourself familiar with debugging tools. It will help you and boost your development skills and quality of your code, as well as reduce time you spend on fixing it.

Advertisement