Facebook suggests people you may be (or should be) friends with. Netflix suggests movies you might like. Amazon suggests products to buy. How do they do that? In this assignment, you will learn one simple way to make such suggestions. Representing a social network as a graph A graph or network represents relationships among things. The things are represented as nodes or vertices, and the relationships are represented as edges. One common use for a graph is to represent friendship among people in a social network. For example, here is the friendship graph for some of the characters of "Romeo and Juliet": Nurse Juliet 10 12 Capulet Tybalt Romeo Friar Laurence Benvolio 12 Montague Escalus Mercutio 8 Paris An edge between person A and person B means that A considers B a friend, and also B considers A a friend. A weight of an edge represents the closeness of two friends. The higher the score is the closer the two friends are. Recommending friends Your tasks are: 1. Build a graph to store the above Romeo and Juliet graph. You can use method Edge List or Adjacency List or Adjacency Matrix. (30 Points) 2. Recommend friends by closeness. (70 Points) For example, Capulet is in the recommendation list of Mercutio. The closeness between Capulet and Mercutio should be: 5(Mercutio-Paris)+3(Paris-Capulet) + 9(Mercutio-Escalus) + 2(Escalus- Capulet) You will ask user to type a name. For example: "Please type a name, and a recommendation list of people based on closeness will be displayed!" Then you will produce and print friend recommendations for this user based on closeness. For example, for Mercutio the list should be: Montague 32 Juliet 25 Friar Laurence 21 Capulet 19 Benvolio 12 3. You might find it necessary to implement the following methods in your classes, to create the method for task 2: 1) FriendCloseness: Prints the friends' names and the closeness. For example, Capulet is a friend of Paris, and the closeness is 3. 2) FriendsofFriends: Returns a friends of friends list. For example, Capulet should be in the friends of friends list of Mercutio. (Friends and self should not be put in this list); 3) CommonFriends: Returns a list of common friends of two people. For example, Mercutio has two friends in common with Capulet (Escalus and Paris); 4) NumberofCommonFriends(): Returns the number of common friends. For example, the number of common friends between Mercutio and Friar Laurence is one (Romeo); 5) Recommendby NumberofCommonFriends(): Prints recommended friends by number of common friends. You can do this by assigning each potential friend a number called a score (number of common friends), where higher scores indicate a better match. Then you can sort your list according to the score. Given user X, if two people Y and Z would be equally good as new friends for X (they have the same score), then they should be listed in alphabetical order (for names). For example, for Mercutio the list should be: Capulet Montague Benvolio Friar Laurence Juliet