Java says index 3 out of bounds for length 3 in ford-fulkerson algorithm

Question

Hey I am implementing ford-fulkerson algorithm and finding the max flow. I am simply reading some input from a text file name as bridge and finding the maximum flow but it's showing error of Index 3 out of bounds for length 3. The error is in line 24 it's saying and I am not getting why it's showing the error. Anyone please help with this. I have tried my best but I am not getting the exact solution of it.

Here is my code:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class MaxFlow {
    boolean[] found;
    int N;
    int[][] cap;
    int[][] flow;
    int[] dad;
    int[] dist;

    boolean searchFattest(int source, int sink) {
        Arrays.fill(found, false);
        Arrays.fill(dist, 0);
        dist[source] = Integer.MAX_VALUE / 2;
        while (source != N) {
            int best = N;
            found[source] = true;
            if (source == sink) break;
            for (int k = 0; k < N; k++) {
                if (found[k]) continue;
//                  System.out.println("cap: "+cap[source][k] + " flow: "+flow[source][k]);
                int possible = Math.min(cap[source][k] - flow[source][k], dist[source]);
                if (dist[k] < possible) {
                    dist[k] = possible;
                    dad[k] = source;
                }
                if (dist[k] > dist[best]) best = k;
            }
            source = best;
        }
        return found[sink];
    }

    boolean searchShortest(int source, int sink) {
        Arrays.fill(found, false);
        Arrays.fill(dist, Integer.MAX_VALUE/2);
        dist[source] = 0;
        while (source != N) {
            int best = N;
            found[source] = true;
            if (source == sink) break;
            for (int k = 0; k < N; k++) {
                if (found[k]) continue;
                if (cap[source][k] - flow[source][k] > 0) {
                    if (dist[k] > dist[source] + 1){
                        dist[k] = dist[source] + 1;
                        dad[k] = source;
                    }
                }
                if (dist[k] < dist[best]) best = k;
            }
            source = best;
        }
        return found[sink];
    }

    public int getMaxFlow(int[][] cap, int source, int sink) {
        this.cap = cap;
        N = cap.length;
        found = new boolean[N];
        flow = new int[N][N];
        dist = new int[N+1];
        dad = new int[N];

        int totflow = 0;
        while (searchFattest(source, sink)) {
            int amt = Integer.MAX_VALUE;
            for (int x = sink; x != source; x = dad[x])
                amt = Math.min(amt, cap[dad[x]][x] - flow[dad[x]][x]);
            for (int x = sink; x != source; x = dad[x]) {
                flow[dad[x]][x] += amt;
                flow[x][dad[x]] -= amt;
            }
            totflow += amt;
        }

        return totflow;
    }

    public static void main(String[] args) throws FileNotFoundException {
        MaxFlow flow = new MaxFlow();
        Scanner s = new Scanner(new File("C:\\Users\\Lenovo\\Documents\\bridge.txt"));
        int rows = 9;
        int columns = 3;
        int [][] myArray = new int[rows][columns];
        while(s.hasNextLine()) {
           for (int i=0; i<myArray.length; i++) {
              String[] line = s.nextLine().trim().split(" ");
              for (int j=0; j<line.length; j++) {
                 myArray[i][j] = Integer.parseInt(line[j]);
              }
           }
        }
        System.out.println(Arrays.deepToString(myArray));
//        int[][] cap = {{0},{1}};
        System.out.println(flow.getMaxFlow(myArray, 0, 5));
    }
}

Here is the error it is showing:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
at MaxFlow.searchFattest(MaxFlow.java:24)
at MaxFlow.getMaxFlow(MaxFlow.java:68)
at MaxFlow.main(MaxFlow.java:98)

Here is the input file that I am reading: bridge.txt

Java arrays are 0 based. 0 is the first valid index, LENGTH-1 is the last valid index, LENGTH isnt valid any more. And note: please understand that *any* error you are running into ... most likely has been asked here before. Simply try to put (parts of) the exception message into your favorite search engine. You can find good answers/explanations for "all" basic errors much faster than it takes to write up a good question. — GhostCat, Mar 29 '21 at 08:47
Having said that: this is really a nice question. It contains the code, the error, the output. Great work! — GhostCat, Mar 29 '21 at 08:48
Finally: always follow java naming conventions. Sure, math formulas use names like *N*, but the field in a java class should always go camelCase, and ideally: use more than 1 letter. Also: try to go with a minimum number of fields, be really careful about having multiple methods "fill" different fields of your class. — GhostCat, Mar 29 '21 at 08:49
@GhostCat I thank you for your effort and I know the concept of array but I am not getting why the error is occurring ? Can you please elaborate your answer. — arif hussain, Mar 29 '21 at 11:00
Look at your source code, which line is *24*. Look what it is doing. For *some* reason it is using 3 as index, probably because in some other place, you count up to length, instead of length-1. Thing is: when you dont understand what your code is doing ... then you have to enable yourself to find out. For example by using a debugger and stepping through the code execution. or simply by adding print statements. — GhostCat, Mar 29 '21 at 11:02
You see, that exception tells you that something in your code is wrong. The *real* answer now is to *debug* your code, to determine where it does the wrong thing. Sure, somebody here *could* do that work. But learning programming is ALSO about debugging code. In other words: delegating this work to other people means you do not learn how to do it yourself. — GhostCat, Mar 29 '21 at 11:03
@GhostCat Ok great I will thank you so much for your effort really appreciated. — arif hussain, Mar 29 '21 at 11:04

Java says index 3 out of bounds for length 3 in ford-fulkerson algorithm

0 Answers0