CS19002 Programming and Data Structures Laboratory |
Spring 2010, Section 5 |

A house has *n* rooms numbered 0,1,2,`...`,*n*-1.
Between some pairs (*i*,*j*) of rooms, there exist connecting
doors. Each door is assumed to be a bidirectional link between the two
rooms it connects. Your task is to find out the complete connectivity
pattern of the rooms.

For example, consider 10 rooms with initial connectivity as show below.

1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1

Of course, every room is connected to itself. Moreover, rooms *i*
and *j* are connected if there is a door between these rooms. For example,
there is a door between rooms 0 and 2.

Using multiple doors, one can reach a room from another even if these two rooms do not share a common door. For example, rooms 0 and 2 share a door, and so also do rooms 2 and 5 and rooms 5 and 4. Therefore, the rooms 0 and 4 are connected. The final connectivity matrix of the above 10 rooms is as follows.

1 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0 1

From this matrix, the groups of connected rooms can be identified as follows.

0 2 4 5 6 9 1 3 7 8

In order to solve this problem, proceed as follows.

Use the following random function.

#include <stdio.h> #include <stdlib.h> #include <time.h> #define NROOMS 40 #define PROBIND 20 void genDoors ( int A[][NROOMS] ) { int i, j; srand((unsigned int)time(NULL)); for (i=0; i<NROOMS; ++i) { A[i][i] = 1; for (j=i+1; j<NROOMS; ++j) { A[i][j] = A[j][i] = (rand() % PROBIND) ? 0 : 1; } } }

Write a function with the prototype

void printConn ( int A[][NROOMS] );

to print the initial and final connectivity patterns.

Write a function with the prototype

void boolMul ( int A[][NROOMS], int B[][NROOMS], int C[][NROOMS] );

to compute the Boolean product of A and B and store the result in C.
Both the input matrices may be the same, and the output may be the same
as one (or both) of the inputs.
If A stores the connectivity among rooms using <=*r* doors,
and B the same using <=*s* doors, then the product C should
store the connectivity among rooms using <=*r*+*s* doors.
We have

C[i][j] = OR_{0<=k<=n-1}(A[i][k] AND B[k][j]).

Since there are *n* rooms, two connected rooms are connected
by no more than *n*-1 doors. So it suffices to compute the
*l*-fold Boolean product of the initial connectivity matrix
with itself for any *l*>=*n*-1.

Write a function with the prototype

void checkConn ( int A[][NROOMS] );

int main () { int A[NROOMS][NROOMS], len; /* Generate doors randomly */ genDoors(A); printf("Initial connectivity:\n"); printConn(A); /* Compute connectivity via Boolean multiplication */ len = 1; while (len < NROOMS-1) { boolMul(A,A,A); len *= 2; } printf("Final connectivity:\n"); printConn(A); /* Identify connected groups of rooms */ checkConn(A); exit(0); }

Report the output of your program for 40 rooms.

Lab Home | Submission Site | My Home |