Assignment 3: Social Networks

Due Date: Tuesday 5 December 2017 before 9:00pm

This assignment must be completed alone (no partners). Please see the syllabus for information about academic offenses.

Introduction

In this assignment, you'll write a friend recommendation system for a social network. Based on the scoring system described below, your program will recommend people that a person may wish to befriend.

The purpose of this assignment is to give you practice using the programming concepts that you have seen in the course so far, including (but not limited to) files, dictionaries and dictionary methods, and unit testing.

This handout explains the problem you are to solve, and the tasks you need to complete for the assignment. Please read it carefully.

Starter Code

As in previous assignments, we are providing a zip archive for you download that contains the assignment starter code.

Test Files: test_get_average_friend_count.py and test_get_families.py

We are providing the beginning of two unit test files, test_get_average_friend_count.py and test_get_families.py. These files will contain your unit tests for the get_average_friend_count(...) and get_families(...) functions, respectively, that are described below.

Main Program: friend_finder.py

The friend_finder.py file contains a main block that loads some data and then calls some functions that you are to write for this assignment. You do not need to modify this file. After you have implemented all of your functions, run this file to interactively test different profiles.

Required and Helper Functions: network_functions.py

The network_functions.py file contains the headers for the functions you will need to write for this assignment, and one completed function docstring. You will start development here, using the Function Design Recipe process to implement each required function. The functions in this file can call each other, and several of them will also be called by the main program (friend_finder.py). You can, and should, write some helper functions in this file that are called by your required functions.

Data: profiles.txt

The profiles.txt file contains social network data in a block format. This is sample data, and you should not modify this file. You may want to create your own data files to supplement this file for testing. See the next section for instructions on how to interpret this data.

Checker: checker.py

We have provided a checker program (checker.py) that tests two things:

The checker program does not test the correctness of your functions, so you must do that yourself.

Data Format

The profile information for people in the social network will be stored in a file and your program will need to read the data from the file and process it.

The file will contain 0 or more people profiles. Each profile will have the following format:

The profile file format will always adhere to the following rules:

The starter zip file contains an example profile file named profiles.txt.

Your Tasks

You are to write six required functions in network_functions.py and also a suite of unit tests for two of those functions.

Required Testing (unittest)

Write (and submit) unittest testfiles for functions get_average_friend_count(...) and get_families(...). These tests should be implemented in the appropriately named starter files.

We will evaluate the completeness of your test files by running them against flawed implementations we have written to see how many errors you catch. Avoid redundant tests. The goal is to catch all of our errors without extra, unnecessary tests.

Your unittest testfiles should stand alone: they should require no additional files (like a profile file). Instead, you should define appropriate test values in the file, such as a dictionary that might be generated from reading a profile file, to use for your tests. You may assume that the folder that contains your unittest testfiles also contains a network_functions.py file.

Alphabetical Order

In the functions below, where alphabetical order is specified, you should use the list method sort. As a result, the empty string would come before non-empty strings, and uppercase names like 'DJ Tanner' would come before mixed-case names like 'Danny Tanner'.

Required Functions

This section contains a table with detailed descriptions of the 6 functions that you must complete. These are the functions that we will be testing. However, you should follow the approach we've been using on large problems recently and write additional helper functions to break these high-level tasks down. Each helper function must have a clear purpose. Each helper function must have a complete docstring produced by following the Function Design Recipe. You should test your helper functions to make sure they work.

Function name:
(Parameter types) -> Return type
Detailed description
load_profiles:
(TextIO,
Dict[str, List[str]],
Dict[str, List[str]]) -> None
The file parameter refers to a file that is open for reading. The data in the file is in the Data Format described above. The second parameter is a "person to friends" dictionary and the third parameter is a "person to networks" dictionary. Update the two dictionaries by adding the data from the open file to them. Note: it may turn out that person A has person B in their friends list, while person B does not have person A in their friends list.

The two dictionaries listed below result from adding the data in the example file profiles.txt to two empty dictionaries:

  • "person to friends":
    • key: person's name in "FirstName(s) LastName" format (str)
    • value: list of friends' names in "FirstName(s) LastName" format (List[str]) in alphabetical order by "FirstName(s) LastName". Use the list method sort to put the list of friends' names into alphabetical order.
    • example: {'Jay Pritchett': ['Claire Dunphy', 'Gloria Pritchett', 'Manny Delgado'], 'Claire Dunphy': ['Jay Pritchett', 'Mitchell Pritchett', 'Phil Dunphy'], 'Manny Delgado': ['Gloria Pritchett', 'Jay Pritchett', 'Luke Dunphy'], 'Mitchell Pritchett': ['Cameron Tucker', 'Claire Dunphy', 'Luke Dunphy'], 'Alex Dunphy': ['Luke Dunphy'], 'Cameron Tucker': ['Gloria Pritchett', 'Mitchell Pritchett'], 'Haley Gwendolyn Dunphy': ['Dylan D-Money', 'Gilbert D-Cat'], 'Phil Dunphy': ['Claire Dunphy', 'Luke Dunphy'], 'Dylan D-Money': ['Chairman D-Cat', 'Haley Gwendolyn Dunphy'], 'Gloria Pritchett': ['Cameron Tucker', 'Jay Pritchett', 'Manny Delgado'], 'Luke Dunphy': ['Alex Dunphy', 'Manny Delgado', 'Mitchell Pritchett', 'Phil Dunphy']}

  • "person to networks":
    • key: person's name in "FirstName(s) LastName" format (str)
    • value: list of networks that person belongs to (List[str]) in alphabetical order. Use the list method sort to put the network names into alphabetical order.
    • example: {'Claire Dunphy': ['Parent Teacher Association'], 'Manny Delgado': ['Chess Club'], 'Mitchell Pritchett': ['Law Association'], 'Alex Dunphy': ['Chess Club', 'Orchestra'], 'Cameron Tucker': ['Clown School', 'Wizard of Oz Fan Club'], 'Phil Dunphy': ['Real Estate Association'], 'Gloria Pritchett': ['Parent Teacher Association']}

    Notes:

    • You do not need to finish this function before working on the rest of the assignment. If you get stuck on this function, move on to the next one and come back to it.
    • The given dictionaries may or may not be empty.
    • The given dictionaries may contain a person who also appears in the file. Add to the given dictionaries, but do not insert duplicate friends or networks.
    • In the "person to friends" dictionary, each person must not have duplicate friends' names in their friends list.
    • Simliarly, in the "person to networks" dictionary, each person must not have duplicate network names in their networks list.
    • If a person does not have any friends, then they must not appear in the "person to friends" dictionary.
    • Similarly, if a person does not belong to any networks, then they must not appear in the "person to networks" dictionary.

get_average_friend_count:
(Dict[str, List[str]]) -> float
Return the average number of friends that people who appear as keys in the given "person to friends" dictionary have.
get_families:
(Dict[str, List[str]]) -> Dict[str, List[str]]
Return a "last name to first names" dictionary based on the given "person to friends" dictionary. The returned dictionary should contain every person whose name appears in the given dictionary (as a key or in a value list). The keys in the returned dictionary should be the last names of people in the given dictionary. (Remember: every person has exactly one last name.) The values are lists of the first names (in alphabetical order) of people with a given last name. Names in the list should be unique: no one should be listed more than once. Use the list method sort to put the lists of first names into alphabetical order.
invert_network:
(Dict[str, List[str]]) -> Dict[str, List[str]]
Return a "network to people" dictionary based on the given "person to networks" dictionary. The values in the dictionary are sorted alphabetically.

The example dictionary below is based on example file profiles.txt.
  • "network to people":
    • key: network (str)
    • value: sorted list of people belonging to that network in "FirstName(s) LastName" format (List[str]). Use the list method sort to put the names into alphabetical order.
    • example: {'Parent Teacher Association': ['Claire Dunphy', 'Gloria Pritchett'], 'Chess Club': ['Alex Dunphy', 'Manny Delgado'], 'Law Association': ['Mitchell Pritchett'], 'Orchestra': ['Alex Dunphy'], 'Clown School': ['Cameron Tucker'], 'Wizard of Oz Fan Club': ['Cameron Tucker'], 'Real Estate Association': ['Phil Dunphy']}
get_friends_of_friends:
(Dict[str, List[str]], str) -> List[str]
Given a "person to friends" dictionary and the name of a person (in the same format as the dictionary keys), return the list of names of people who are friends of the named person's friends. The returned list should be sorted in alphabetical order and should not contain the original person. The name of a friend of a friend should appear in the returned list once for each mutual friend. (That is, names may be listed more than once in the returned list.) Use the list method sort to put the names into alphabetical order.
make_recommendations:
(str, Dict[str, List[str]], Dict[str, List[str]]) -> List[Tuple[str, int]]
The first parameter is a person's name (in the same format as the dictionary keys), the second parameter is a "person to friends" dictionary, and the third parameter is a "person to networks" dictionary. Using the recommendation system described below, return the friend recommendations for the given person as a list of tuples where the first element of each tuple is a potential friend's name (in the same format as the dictionary keys) and the second element is that potential friend's score. Only potential friends with non-zero scores should be included in the list. The recommendations should be sorted from highest to lowest score. If multiple people have the same score, they should be sorted alphabetically. The person given as the first argument may be a key in zero, one, or both of the given dictionaries.

Recommendation score

For each person, all people who they are not currently friends with are potential friends. For a particular person, each potential friend is scored using the following point system:

  • For every mutual friend that the person and the potential friend have, add 1 point to the potential friend's score
  • For each network that the person and the potential friend both belong to, add 1 point to the potential friend's score
  • If the person has the same last name as the potential friend, add 1 point to the potential friend's score, but only if they have something else in common (mutual friend(s), mutual network(s), or both).

Mutual friend definition (Added 13 November 2017)

We will say that person A is a mutual friend of person B and person C if and only if

  1. person B has person A in their friends list and person A has person C in their friends list, or
  2. person C has person A in their friends list and person A has person B in their friends list, or
  3. both 1. and 2. are satisfied.
In the first relationship, person C is a friend of a friend of person B, and in the second relationship, person B is a friend of a friend of person C.

Let's consider the example "person to friends" dictionary from before:
{'Jay Pritchett': ['Claire Dunphy', 'Gloria Pritchett', 'Manny Delgado'], 'Claire Dunphy': ['Jay Pritchett', 'Mitchell Pritchett', 'Phil Dunphy'], 'Manny Delgado': ['Gloria Pritchett', 'Jay Pritchett', 'Luke Dunphy'], 'Mitchell Pritchett': ['Cameron Tucker', 'Claire Dunphy', 'Luke Dunphy'], 'Alex Dunphy': ['Luke Dunphy'], 'Cameron Tucker': ['Gloria Pritchett', 'Mitchell Pritchett'], 'Haley Gwendolyn Dunphy': ['Dylan D-Money', 'Gilbert D-Cat'], 'Phil Dunphy': ['Claire Dunphy', 'Luke Dunphy'], 'Dylan D-Money': ['Chairman D-Cat', 'Haley Gwendolyn Dunphy'], 'Gloria Pritchett': ['Cameron Tucker', 'Jay Pritchett', 'Manny Delgado'], 'Luke Dunphy': ['Alex Dunphy', 'Manny Delgado', 'Mitchell Pritchett', 'Phil Dunphy']}

For this dictionary, here is an example of a mutual friend:

Testing your Code

It is strongly recommended that you test each function as soon as you write it. As usual, follow the Function Design Recipe (we've provided the function name and types for you) to implement your code. Once you've implemented a function, run it against the examples in your docstrings and the unit tests you've defined.

Additional requirements

Marking

These are the aspects of your work that will be marked for Assignment 3:

What to Hand In

Submit the files network_functions.py, test_get_average_friend_count.py and test_get_families.py on MarkUs by the due date. Follow the instructions on the course website and make sure the files are named appropriately. The very last thing you do before submitting network_functions.py should be to run the checker program one last time. The very last thing that you should do before submitting test_get_average_friend_count.py and test_get_families.py is to run them one last time. Otherwise, you could make a small error in your final changes before submitting that causes your code to receive zero for correctness or testing.