"Two-pass algorithm" implementation in Java

I'm rather new to Java and to algorithms in general. I implemented the so called Two-pass algorithm, and want to know if there are improvements to my way of implementing it. What it does is it takes a matrix of ones and zeros and replaces all ones by labels. All ones that are connected should be labeled with the same label. Each such component should have a unique label. The end result can be visualized by replacing each label with a color, like this:

I followed as closely as I could the pseudo-code available in this section of the Wikipedia article. But are there improvements?

```
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class MatrixComponents {

public int[][] labeledMatrix;

public MatrixComponents(int[][] matrix) {
ArrayList> linked = new ArrayList>();
int[][] labels = new int[matrix.length][matrix[0].length];

int NextLabel = 0;

//First pass
for(int i=0; i neighbors = new ArrayList();
for(int ni=-1; nilabels.length-1 || j+nj>labels[0].length-1) {
continue;
}
else {
if(i+ni == 0 && i+nj == 0) continue;
if(labels[i+ni][j+nj] != 0) neighbors.add(labels[i+ni][j+nj]);
}
}
}

if(neighbors.size() == 0) {
ArrayList tempArrayList = new ArrayList();
tempArrayList.add(NextLabel);
linked.add(NextLabel, tempArrayList);
labels[i][j] = NextLabel;
NextLabel++;
}
else {

labels[i][j]=1000*1000;
for(int neighbor : neighbors) {
if(neighbor EquivalentLabels = linked.get(labels[i][j]);

Declare by interface and not implementation

Instead of

ArrayList> linked = new ArrayList>();

use:

List> linked = new ArrayList>();

Or, if you're using Java 7+:

List> linked = new ArrayList<>();

Edit: When looking at your code a bit more, with all the union method and stuff going on, I wonder if it perhaps should be List> right from the start, so that you could use

linked.get(neighbor).addAll(neighbors);

instead of what you currently do:

linked.set(neighbor,union(linked.get(neighbor),neighbors));

Algorithmically speaking, this part:

//First pass
for(int i=0; i<matrix.length; i++) {
    for( int j=0; j<matrix.length; j++) {
        labels[i][j] = 0;
    }
}

Is a) Not part of the first pass. b) Totally unnecessary as the labels array is filled with zeros already. c) Buggy if matrix is not square.

int[][] matrix = {{0, 0, 0, 0, 1, ...

I'd highly recommend reading from a file instead of hardcoding into the code!

Your constructor and your main method is doing way too many things, break up the code into additional methods.

Some methods can include:

• Read matrix from file / some input / code

• One (or more) methods for doing the "first pass" (you can put the 2d outer loop in one method, which can call another method)

• One method for the "second pass"

• One method for the output

public int[][] labeledMatrix;

Don't use public fields like that, that one should be private. It's good to restrict the visibility as much as possible.

i and j vs. x and y

Sometimes 2d arrays are indexed as matrix[x][y] and sometimes as matrix[y][x], to make it clear which version you're using, don't use i and j. I really don't like those variable names when using 2d arrays.

It is a good practice to always use braces, even for one-liners: (Even I get told this from time to time!)

if(i+ni == 0 && i+nj == 0) continue;
if(labels[i+ni][j+nj] != 0) neighbors.add(labels[i+ni][j+nj]);

Is changed to:

if (i + ni == 0 && i + nj == 0) {
    continue;
}
if (labels[i + ni][j + nj] != 0) {
    neighbors.add(labels[i + ni][j + nj]);
}

Remember the comments about the naming though.

For your drawing an image plans, you should read up on Creating and Drawing to an Image and the chapter that follows it Writing/Saving an Image. You can use the Graphics2D object as shown in the first link to draw rectangles on the image.

if(neighbors.size() == 0) {

is the same as

if (neighbors.isEmpty()) {

StackExchange Code Review Q#55250, answer score: 15