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.
- Implement Disjoint Set with:
make_set(i)find_set(i)union_sets(i, j)final_sets()
- Analyze the binary image to:
- Display original image
- Label and display connected components
- Sort and display components by size
- Display components with size > 2
- Display components with size > 11
| 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 |
./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.
Your program will output the following, in order:
- The binary image from
infile - Connected components with unique character labels
- Component sizes sorted by size
- Image with components of size > 2
- Image with components of size > 11
Set representative of 4: 2 Set representative of 6: 5 Total sets: 7 For academic use only — Western University, CS 3340b: Analysis of Algorithms