DESCRIPTION OF THE DATA STRUCTURE

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

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

values array:

•    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:

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

We use –1 in the rowPos array to indicate the fact that a row does not contain any non-zero values.

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

colPos array:

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.

INSTRUCTIONS AND GUIDELINES

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:

Programming Objectives:

1.   All code must be written in standard C++ (so that it can be compiled by a g++ compiler).

2. You have to submit: A file named HW1_CS2413.cpp that contains all the code of this project.

3. You are provided: A file named template1.cpp including the template your submission should follow, as well as sample input and output files of your program. These files will be available in Module “Projects” in Canvas.

4.   You will create a class named CRM (using the given template file) that has fields for the three

arrays.

5.   The class will have several methods, including finding the most influential user (i.e., the user whose posts have been retweeted the most times), finding the most active user (i.e., the user who has made the largest number of retweets), ranking the users in a descending order based on how influential they are, as well as ranking them based on how active they are. The latter two methods should compute a vector of all users, sorted according to their ranking. In case of ties, you can rank the users in ascending order of their id (i.e., 0, 1, 2, 3, …).

6.   All input will be read via redirected input. That is, you should not open a file inside the program.