Assignment 2: Connected Components in a Binary Image

Overview

This project implements an efficient Disjoint Set (Union-Find) data structure to identify connected components in a binary image. The algorithm uses union by rank and path compression to optimize disjoint set operations. The program reads a binary image from an ASCII file and outputs labeled components based on size.

Requirements

• Implement Disjoint Set with:
  • make_set(i)
  • find_set(i)
  • union_sets(i, j)
  • final_sets()
• Analyze the binary image to:
  1. Display original image
  2. Label and display connected components
  3. Sort and display components by size
  4. Display components with size > 2
  5. Display components with size > 11

Files

File Name	Description
uandf.java	Java implementation of Disjoint Set with union by rank + path compression
uandf.class	Compiled version of uandf.java (optional to upload)
asn2	Shell script to compile and run the program (or just runs Java file)
asn2Script.sh	Unix script output showing sample program execution
asn2_solution.pdf	PDF containing answers to theoretical questions (Q1–Q8)
infile	Input ASCII file representing the binary image
asn2.pdf	Assignment instructions

How to Run

./asn2 < infile

• The script will compile (if needed) and execute your program using the provided image in infile.
• The program is expected to work on compute.gaul.csd.uwo.ca.

Output

Your program will output the following, in order:

1. The binary image from infile
2. Connected components with unique character labels
3. Component sizes sorted by size
4. Image with components of size > 2
5. Image with components of size > 11

Sample Output (from asn2Script.sh)

Set representative of 4: 2
Set representative of 6: 5
Total sets: 7

License

For academic use only — Western University, CS 3340b: Analysis of Algorithms