Twitter is a popular social media platform for users to send out a short message (a "tweet") to other users who are registered as his/her followers. Figure 1 shows a graph. (The topic on graphs will be covered after your term break, and you are not required to understand graphs for this lab; it's a very useful illustration for this scenario nonetheless).
The circles labeled "0", "1", "2" etc. are called nodes (or vertices) of the graph, and the arrows connecting the nodes are called edges. This graph shows a small network of Twitter users with the nodes representing users, and the edges show which user is following which other users: an arrow means "is following" (and not "is followed by"). The graph in figure 1 can hence be interpreted as a network of 11 tweeter users (users 0, 1, 2... 10). Users 0 and 3 are following 1, 1 is following 2, 3 and 4, 2 is following 0 and 3, and so on. By studying this simple graph, it should be obvious that user 3 has the most number of followers (four followers), and is hence the most influential user since a tweet initiated by user 3 will be received by four users.
We would like to start a viral marketing campaign. The approach is to select five Twitter users, and pay them to tweet an advertisement. The problem is to identify which five users to select so that we will reach as many unique followers as possible.
For simplicity, assume that Tweeter user IDs are sequential numbers starting from 0. So if there are 11 users, their user IDs will be 0, 1, 2... 10. The Tweeter graph above can be represented in the form of a table like this:
|
User ID
|
Direct Follower User IDs
|
|
0
|
2
|
|
1
|
0, 3
|
|
2
|
0, 1
|
|
3
|
1, 2, 4, 5
|
|
4
|
1, 6, 10
|
|
5
|
|
|
6
|
7, 8
|
|
7
|
|
|
8
|
|
|
9
|
8
|
|
10
|
9
|
Instead of selecting only five Tweeter users to send the advertisement, management has approved a budget to pay many more Tweeter users to send the advertisement. However this time round, management wants EVERY user to get the message. So, the new goal for you is to select the smallest number of Tweeter users who need to send the advertisement so that everyone will get it.
Requirements:
Write a method called select_set that takes in 1 parameter: followers (a 2D array of Tweeter users) and returns the user IDs of any number of users (as an array of integers) selected by your algorithm who will be selected to broadcast the advertisement. followers.length will give you the total number of Tweeter users in the Tweeter universe.
The objective is to make select_set as small as possible such that every user gets the advertisement.
Your solution will be checked using this method: all_users_got_message?. This method takes in your array of selected tweeters (selected) and the original followers 2D array, and returns true (if every Tweeter user would have gotten the message) or false (if at least one Tweeter user hasn't gotten the message). If all_users_got_message?istrue, your solution's quality will depend on the number of users in your selected set (selected.length).
Attachment:- Project Assignment.rar