University of Arizona, Department of Computer Science

CSc 120: Friends

The primary purpose of this problem is to work with linked lists.

Background

Social media sites often look at what you have in common with your friends (or followers, or contacts) to make suggestions. As an example, Facebook and LinkedIn will point out "mutual friends", i.e., people whose friends have one or more people in common with yours. This problem involves implementing a simple form of an algorithm for identifying such mutual friends.

Expected Behavior

Write a Python program, in two files linked_list.py and friends.py, that behaves as specified below. The file linked_list.py should contain code implementing the LinkedList and associated classes while friends.py should contain code that uses these classes to implement the functionality required of this program. At the top your friends.py file, include the following statement so that you are able to use the classes in your linked list file:

from linked_list import *

Your program should behave as follows.

Read in the name of an input file using input('Input file: '). Read in the contents of this file into your program, e.g, as a list.
Organize the data, which specify friendship relationships between pairs of names, and organize the data as specified under Data structures below.
NOTE: Friendships are two-way relations (in mathematics, such relations are called symmetric). This means that for each input line of the form
X Y
you should set up your data structures to indicate two things:
- X is a friend of Y; and
- Y is a friend of X.
Read in two names using the function calls below. You can use other variable names or your choice to store the values read in. Strip off whitespace as necessary.
name1 = input('Name 1: ') name2 = input('Name 2: ')
If there are friends in common, first print the following line:
```
    Friends in common: 
```
Then print out the name of each mutual friend of name1 and name2, i.e., any name3 such that name3 is a friend of both name1 and name2 (see Output format below). Names can be printed in any order.
If there are no friends in common, no further output is produced. (That is, if there are no friends in common, the program only produces the input prompts.)

Input format

Each line in the input file consists of two strings separated by whitespace (blanks and tabs). E.g.: the file in04 is:

William Ethan Rebecca Lindsey William Lindsey William Patrick

You should not make assumptions about the amount of whitespace around and between names.

Output format

Names of mutual friends should be printed out one per line, in any order, using the following statement:

print(name)

Data Structures

The names read in should be organized as a linked list with a node per name. Each node should have the following attributes:

a name (a string);
the friends for that name (a linked list); and
a reference to the next node.

For example, for the file in04 mentioned above (under Input format), the data structure should be as shown below:

(click on the image for a larger picture)

Programming Requirements

Your program should use linked lists to implement:

the list of the names read in from the input file; and
for each such name, the list of that person's friends.

Your code should be organized among your files as follows:

linked_list.py: Code to implement the linked list class.
friends.py: Code that uses methods from the linked list class to implement the application required by this assignment.

The methods defined in linked_list.py can be accessed in friends.py using an import statement in the latter file.

Errors

In order to facilitate grading, we will use specific error messages in this assignment, as indicated below.

The following are errors:

Input file cannot be read.
Program behavior: Use a try statement to detect this. Give the following error message and quit.
Error message: "ERROR: Could not open file " + filename
One or both of the names name1 or name2 cannot be found in the list of names. (Read in both names first. Check for name1 first and name2 second. At most one name will be unkown.)
Program behavior: Give the following error message and quit.

Error message: "ERROR: Unknown person " + name

The tester will fully exercise all error cases that we expect you to handle. In other words, if you pass all error-producing tests, you can assume your error handling is fully correct and complete.

Examples

Some examples are shown here.