Unresolved Compilation Problem

[Neyla Adam]

Hi!
My network flow problem doesn't seem to work because of an unresolved compilation problem.


this is the code:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

public class Main5 {

	static int numVer; // the number of vertices in the graph
	static ArrayList<Integer> graph[]; // flow is computed on this graph
	static int[][] capacity, flow;

	// Compute a path with positive residual capacity using BFS
	// Return true if such a path exists and false otherwise
	public static boolean augmentingPathExists(int previousVertexOnPath[]) {
		// Allocate space for auxilary data structures
		LinkedList<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[numVer];

		// Initialization of auxilary data structures
		for (int i = 0; i < numVer; i++)
			visited[i] = false;
		queue.add(0);
		visited[0] = true;

		// BFS
		while (!queue.isEmpty()) {
			int v = queue.poll();
			for (int w : graph[v])
				if (!visited[w] && capacity[v][w] > flow[v][w]) {
					visited[w] = true;
					previousVertexOnPath[w] = v;
					queue.add(w);
					if (w == numVer - 1)
						return true;
				}
		}

		return false;
	}

	// Computes the value of a maximum flow
	public static int computeMaximumFlow() {
		int i, flowOnPath;
		// Find paths with BFS and return path in previousVertexOnPath array
		int[] previousVertexOnPath = new int[numVer];
		// Start with empty flow
		int maxFlow = 0;
		// Use augmenting path P as long as possible
		while (augmentingPathExists(previousVertexOnPath)) {
			// Compute smallest remaining capacity on P
			flowOnPath = Integer.MAX_VALUE;
			for (i = numVer - 1; i != 0; i = previousVertexOnPath[i]) {
				int p = previousVertexOnPath[i];
				flowOnPath = Math.min(flowOnPath, capacity[p][i] - flow[p][i]);
			}
			// Add the smallest remaining capacity to each edge of P
			for (i = numVer - 1; i != 0; i = previousVertexOnPath[i]) {
				int p = previousVertexOnPath[i];
				flow[p][i] += flowOnPath;
				flow[i][p] -= flowOnPath;
			}
			maxFlow += flowOnPath;
		}

		return maxFlow;
	}

	public static void main(String[] args) {
		// Create a new Scanner object for reading the input
		Scanner sc = new Scanner(System.in);

		// Read the number of testcases to follow
		int t = sc.nextInt();

		// Iterate over the testcases and solve the problem
		for (int i = 0; i < t; i++) {

			int numCh = sc.nextInt();
			int numGi = sc.nextInt();
			int numVer = numCh + numGi + 2;

			// Don't forget to initialize numVer
			// Initialize the graph
			capacity = new int[numVer][numVer];
			flow = new int[numVer][numVer];

			graph = (ArrayList<Integer>[]) new ArrayList[numVer];
			for (int ii = 0; ii < numVer; ii++) {
				graph[ii] = new ArrayList<Integer>();
			}

			for (int o = 1; o < numCh; o++) {
				for (int j = 1; j < numCh; j++) {
					graph[0].add(j);
					if (capacity[o][numCh + j] > 1) {
						System.out.println("no");
						System.exit(0);
					}
				}
			}
			for (int k = numCh + 1; k < numVer - 2; k++) {
				graph[k].add(-1);
			}

			// Here add the edges to the graph and initialize capacity and flow!
			// Example:
			// graph[0].add(1); <-- adding an edge from vertex 0 to vertex 1
			// graph[1].add(0); <-- add the reverse edge!
			// flow[0][1] = 0;
			// capacity[0][1] = 1; <- replace 1 with your desired capacity
			// capacity[1][0] = 0; <- the reverse edge should have capacity 0

			// IMPORTANT: Vertex 0 is always considered as the source
			// and vertex numVer - 1 as the sink

			// Compute maximum flow
			int maxFlow;
			int sum = 0;
			maxFlow = computeMaximumFlow();

			for (int z = 1; z < numCh; z++) {
				sum = sum + capacity[0][z];
			}

			if (maxFlow != sum)
				System.out.println("no");

			else
				System.out.println("yes");
			// Output result
		}
	}
}

[Tim Cooke]

Hello Neyla, welcome to the Ranch!

You forgot to tell us what the compilation error you're seeing is?

[Mike London]

I copied your code right in to Intellij and it compiles fine and even runs (waits for input).

What error are you getting?

[Neyla Adam]

Exception in thread "main" java.lang.Error: Unresolved compilation problem:

at aww.Main5.main(Main5.java:67)

that's the error i get in eclipse..

[Swastik Dey]

Does  the class belong to any package named aww?  If so it should be under the package called aww, and we don't see any package statement in your code.

[Mike London]

Swastik Dey wrote:Does  the class belong to any package named aww?  If so it should be under the package called aww, and we don't see any package statement in your code.

That's really strange. I copied and pasted the code right into Intelli and it had no issues and even ran.

Try the community (free) edition of Intellij as a test.

I don't think it's your code.

And, I did zero configuration chores.

-- mike

[Henry Wong]

Just took one of my other code (managed by eclipse), and removed the package statement, but still kept it in the package. Eclipse will complain about something like "declared package AAA does not match BBB blah blah blah".

Additionally, ran that broken code (even though it has an error)... eclipse will complain, and popup to confirm.. and forced eclipse to run anyway. The resultant error message at console was "unresolved compilation problem: at xxx.yyy.main(zzz.java)".... just like as mentioned by the OP.

So, it is two problems. One, eclipse is configured to expect the class in the package, but with the code, the class is not in the package. And two, the error message is ignored; the application is forced to run, forcing eclipse to print out a nonsensical message, because that information is lost at run time.


Now, is the missing package the underlying cause? or did the OP simply didn't cut and paste it? ... This is not clear. There is no visibility into that. The OP need to tell us what the compilation errors are, and not just tell us the errors when forcing the application to run.

Henry

[Mike London]

Henry Wong wrote:
.
.
.
The OP need to tell us what the compilation errors are, and not just tell us the errors when forcing the application to run.
Henry

Yep, agreed.

[Neyla Adam]

now the compilation problem is solved: i had to declare the package..
now I get those errors though:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
at aww.Main5.augmentingPathExists(Main5.java:24)
at aww.Main5.computeMaximumFlow(Main5.java:50)
at aww.Main5.main(Main5.java:120)

and I do not understand why.. does anyone get it?

[Henry Wong]

Neyla Adam wrote:now the compilation problem is solved: i had to declare the package..
now I get those errors though ... and I do not understand why.. does anyone get it?

The stacktrace gives you tons of information...

Neyla Adam wrote:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
at aww.Main5.augmentingPathExists(Main5.java:24)
at aww.Main5.computeMaximumFlow(Main5.java:50)
at aww.Main5.main(Main5.java:120)

Basically, your main() method called the computeMaximumFlow() method, which called the augmentingPathExists() method. And somewhere in the augmentingPathExits() method, around line 24 of the Main5.java file, you encountered the error.

The error is an ArrayIndexOutOfBounds exception, which is what is thrown when trying to dereference an array. Additionally, you are trying to get element zero, which is the first element of the array. And it failed, which means that the array doesn't have a first element.

Following this, it is likely your "visited" array, which you probably instantiated to hold zero elements. Put a debugging message, either at the instantiation of the array, or before accessing the array, to confirm the size... and you will see the issue.

Henry