Design And Implementation Of A Program For Computing Size Of Connected Components
Essay by 24 • June 1, 2011 • 605 Words (3 Pages) • 1,662 Views
Essay Preview: Design And Implementation Of A Program For Computing Size Of Connected Components
DESIGN AND IMPLEMENTATION OF A PROGRAM FOR COMPUTING SIZE OF CONNECTED COMPONENTS
Title
Computing the size of connected components.
Description
This program takes the input of a twp dimensional grid from a text file. The occupancy of the grid squares in the two dimensional grid determines a shape and I grid square is either occupied or empty. Two occupied squares belong to a same group if they share a common edge. Sp the purpose of this program is to compute the size of all groups in the to dimensional grid. For simplicity, the border squares are assumed to be un-occupied.
Input
This program reads the input from a text file. The first line of the text file must contain the number of rows and the second line should contain the number of columns. The rest of the file contains k lines, each line having equal length containing 0 or 1. An entry of zero represents an empty square and an entry of 1 represents an occupied square. There can be only a maximum of 70 rows and 50 columns inputted by the user.
A sample input text file would look something like this:
10
10
0000000000
0001000110
0011100000
0001000100
0110000100
0000011110
0100000000
0000110010
0100010000
0000000000
Output
The program calculates all the group sizes and prints out a formatted output. The output is also sorted in the ascending order of the group size.
An example of an output
Group Size Number of groups
3
2
1
5 1
6 1
Error Handling
If the program is given a value that is not 0 or 1 in the two-dimensional grid, then it will display an error message.
If the user enters incomplete data then the program will prompt the user to input the rest of the data.
Example
Below is a trace of an execution of the program
10
10
0000000000
0001000110
0011100000
0001000100
0110000100
0000011110
0100000000
0000110010
0100010000
0000000000
Group Size Number
...
...