Assignment 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.

Part 1: Generate the doors

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;
         }
      }
   }

Part 2: Print the matrix

Write a function with the prototype

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

to print the initial and final connectivity patterns.

Part 3: Boolean matrix multiplication

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] = OR0<=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.

Part 4: Identify connected groups of rooms

Write a function with the prototype

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

Part 5: The main() function

   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