In this project we deal with handling sparse matrices. We are interested in nxn matrices that...

Transcribed Image Text:

In this project we deal with handling sparse matrices. We are interested in nxn matrices that represent the 'retweets' that take place among a set of n Twitter users. In particular, the element A[i,j] of matrix A represents the number of times user i has retweeted user j in a specific period. We store these matrices in a data structure called "Compact Retweet Matrix" (CRM), which is explained in detail below. In this project you are asked to define this data structure in a class, together with a set of methods that operate on it. As an example, consider a set of 10 Twitter users and the following 10x10 matrix (consisting of 10 rows and 10 columns, each one numbered using integers from 0 to 9). The non-zero values are in red font just for the sake of clarity. 2 12 0 0 2 0 0 0 0 0 0 0 1 2 3 4 5 6 7 69 0 0 0 0 0 0 0 0 OO 0 8 0 9 37 1 0 0 7 0 0 15 0 0 0 29 values array: 0 1 2 12 5 4 M 3 0 0 0 0 0 0 0 38 0 0 4 7 6 5 4 5 0 0 0 0 0 0 0 0 OO 2 13 1 0 5 0 0 0 0 0 0 0 85 0 0 6 7 8 9 18 15 6 0 4 0 13 0 0 0 0 0 0 7 0 0 0 1 0 54 0 0 0 0 We consider the CRM as a triplet of arrays (values, rowPos, and colpos) which collectively include all the above information. In particular: • The values array has size equal to the number of non-zero values in the matrix, and contains all these values, by the order they appear in the matrix. In the above matrix, there are 18 non-zero values. (The highlighting is used for the connection with the next array, please ignore it for now.) 8 0 0 6 0 18 0 0 92 0 20 10 11 12 13 54 17 38 85 9 0 OO 0 0 0 0 17 0 0 0 0 14 15 16 17 92 37 29 20 • The rowPos array has size equal to the number of users (10 in our case), and for each user it contains the position in values array in which the first nonzero value corresponding to this user appears. The highlighting colors are used in order to help you understand the relation between arrays rowPos and values. rowPos array: 0 1 2 3 4 5 02 8 Therefore, rowPos[0] = 0 indicates that the non-zero values in row 0 of the matrix start being stored at position 0 of the values array. Indeed, it is values[0]-12 and 12 is the first non-zero element in row (user) 0 of the matrix. Similarly, rowPos[1] = 2 indicates that the non-zero values in row 1 of the matrix start at index position 2 of the values array. Indeed, at index position 2 (i.e., values[2]), the value is 4 which is the first non-zero value in row 1. Therefore, the non-zero values of user 0 start from position 0 of the values array and extend up to position 1, since in position 2 we start storing the non-zero values of user 1, and hence they are 12 and 5. In the same spirit, rowPos[7] contains the value 12. This indicates that the first non-zero value in row 7 of the matrix can be found at values[12], which is 38. The non-zero values of user 9 extend from position 15 of the values array until, obviously, the end of it. We use -1 in the rowPos array to indicate the fact that a row does not contain any non-zero values. colPos array: • The colPos array has size equal to the number of non-zero values in the matrix (18 in our case), and for each such value it contains the column of the matrix in which it appears. 0 1 2 3 6 7 8 9 9 -1 12 -1 4 5 24 6 1 8 00 6 7 7 2 6 INSTRUCTIONS AND GUIDELINES 8 9 8 1 00 10 11 12 13 14 15 16 17 7 9 3 5 8 0 1 8 сл 00 Your program should be reading a matrix and it should be storing it in a CRM data structure. Then it should be able to perform queries on this structure. Input format: For the purposes of this project, when we give a matrix as an input, we will be providing that in the sparse format, i.e., a vector (row, col, value) for each non-zero value, indicating the row and column of the matrix in which this value appears. In the first line of the input, we give the total number of rows and the total number of columns of the matrix. For example, for the matrix above the input should be the following: 10 10 18 0212 045 164 217 286 322 36 13 371 4818 5115 5754 5917 73 38 75 85 7892 9037 91 29 98 20 <- Total number of rows and columns <- Total number of non-zero values <- row number, column number and value. (We continue providing one such vector for each non-zero value.) In this project we deal with handling sparse matrices. We are interested in nxn matrices that represent the 'retweets' that take place among a set of n Twitter users. In particular, the element A[i,j] of matrix A represents the number of times user i has retweeted user j in a specific period. We store these matrices in a data structure called "Compact Retweet Matrix" (CRM), which is explained in detail below. In this project you are asked to define this data structure in a class, together with a set of methods that operate on it. As an example, consider a set of 10 Twitter users and the following 10x10 matrix (consisting of 10 rows and 10 columns, each one numbered using integers from 0 to 9). The non-zero values are in red font just for the sake of clarity. 2 12 0 0 2 0 0 0 0 0 0 0 1 2 3 4 5 6 7 69 0 0 0 0 0 0 0 0 OO 0 8 0 9 37 1 0 0 7 0 0 15 0 0 0 29 values array: 0 1 2 12 5 4 M 3 0 0 0 0 0 0 0 38 0 0 4 7 6 5 4 5 0 0 0 0 0 0 0 0 OO 2 13 1 0 5 0 0 0 0 0 0 0 85 0 0 6 7 8 9 18 15 6 0 4 0 13 0 0 0 0 0 0 7 0 0 0 1 0 54 0 0 0 0 We consider the CRM as a triplet of arrays (values, rowPos, and colpos) which collectively include all the above information. In particular: • The values array has size equal to the number of non-zero values in the matrix, and contains all these values, by the order they appear in the matrix. In the above matrix, there are 18 non-zero values. (The highlighting is used for the connection with the next array, please ignore it for now.) 8 0 0 6 0 18 0 0 92 0 20 10 11 12 13 54 17 38 85 9 0 OO 0 0 0 0 17 0 0 0 0 14 15 16 17 92 37 29 20 • The rowPos array has size equal to the number of users (10 in our case), and for each user it contains the position in values array in which the first nonzero value corresponding to this user appears. The highlighting colors are used in order to help you understand the relation between arrays rowPos and values. rowPos array: 0 1 2 3 4 5 02 8 Therefore, rowPos[0] = 0 indicates that the non-zero values in row 0 of the matrix start being stored at position 0 of the values array. Indeed, it is values[0]-12 and 12 is the first non-zero element in row (user) 0 of the matrix. Similarly, rowPos[1] = 2 indicates that the non-zero values in row 1 of the matrix start at index position 2 of the values array. Indeed, at index position 2 (i.e., values[2]), the value is 4 which is the first non-zero value in row 1. Therefore, the non-zero values of user 0 start from position 0 of the values array and extend up to position 1, since in position 2 we start storing the non-zero values of user 1, and hence they are 12 and 5. In the same spirit, rowPos[7] contains the value 12. This indicates that the first non-zero value in row 7 of the matrix can be found at values[12], which is 38. The non-zero values of user 9 extend from position 15 of the values array until, obviously, the end of it. We use -1 in the rowPos array to indicate the fact that a row does not contain any non-zero values. colPos array: • The colPos array has size equal to the number of non-zero values in the matrix (18 in our case), and for each such value it contains the column of the matrix in which it appears. 0 1 2 3 6 7 8 9 9 -1 12 -1 4 5 24 6 1 8 00 6 7 7 2 6 INSTRUCTIONS AND GUIDELINES 8 9 8 1 00 10 11 12 13 14 15 16 17 7 9 3 5 8 0 1 8 сл 00 Your program should be reading a matrix and it should be storing it in a CRM data structure. Then it should be able to perform queries on this structure. Input format: For the purposes of this project, when we give a matrix as an input, we will be providing that in the sparse format, i.e., a vector (row, col, value) for each non-zero value, indicating the row and column of the matrix in which this value appears. In the first line of the input, we give the total number of rows and the total number of columns of the matrix. For example, for the matrix above the input should be the following: 10 10 18 0212 045 164 217 286 322 36 13 371 4818 5115 5754 5917 73 38 75 85 7892 9037 91 29 98 20 <- Total number of rows and columns <- Total number of non-zero values <- row number, column number and value. (We continue providing one such vector for each non-zero value.)