Week 05 Lab Exercise

• To explore an application of graphs
• To get some practice with graph problems
• To perform complexity analysis on graph algorithms
• To implement some basic features of social networks

Marks

5 (see the Assessment section for more details)

Demo

in the Week 5, 7 or 8 lab session

Submit

see the Submission section

Deadline to submit to give

5pm Monday of Week 7

Late penalty

0.2% per hour or part thereof deducted from the attained mark, submissions later than 5 days not accepted

In lectures, we learned that a graph is a collection of vertices and edges between them. This very abstract definition allows for many real-world scenarios and systems to be modelled by graphs - for example, maps, social networks, and the web. In this lab, we will explore an application of graphs in a simple social network app called Friendbook.

Friendbook

Friendbook is a very simple social network app with the following features:

• People can sign up with their name. For simplicity, people are identified by their names, so two people cannot have the same name.
• People can friend other people (i.e., add them as friends). Friending goes both ways, so if you add someone as a friend, you become their friend as well.
• People can unfriend their friends (i.e., remove them from their friends list). This also goes both ways.
• People can see a count of how many friends they have.
• People can see a list of their friends.
• People can see a list of the mutual friends that they share with someone else.
• People can receive friend recommendations. Friendbook has two different methods of generating recommendations:
  1. The first method only recommends friends of friends, and ranks friend recommendations in order of the number of mutual friends, so people who you share more mutual friends with will be recommended first.
  2. The second method recommends friends of friends first, and then friends of friends of friends next, and then friends of friends of friends of friends, and so on. Anyone who can be reached by following friendship links can be recommended.

Names as Vertices

All of the graph implementations we have seen so far have used integer vertices numbered from \( 0 \) to \( n - 1 \), where \( n \) is the number of vertices. This is convenient, as vertex numbers can double as indices into the adjacency matrix or adjacency list. But in Friendbook, the vertices are people (names), so how do we represent this internally?

It turns out we don't need to do that much more work. If we give each person an integer ID between \( 0 \) and \( n - 1 \) and store a mapping between names and IDs, then we can continue to use the graph representations that we are familiar with. A simple way to implement this mapping would be to store all the names in an array, and let the ID of each person be the index containing their name in the array. The first person in the array would have an ID of \( 0 \), the second person in the array would have an ID of \( 1 \), and so on. If we wanted to answer a question involving one or more people, we can scan this array to determine their ID, and then use this ID to query the matrix/list. For example, suppose this is our internal representation:

Now suppose we wanted to find out if Harry and Draco are friends. First, we need to find the vertex numbers associated with Harry and Draco, so we perform a linear scan of the array of names (called labels), and find that Harry is associated with a vertex number of \( 0 \), and Draco is associated with a vertex number of \( 3 \). The adjacency list for vertex \( 0 \) does not contain vertex \( 3 \), so we can conclude that Harry and Draco are not friends.

Unfortunately, this translation between names and vertex numbers adds quite a bit of overhead to our graph operations. Converting from vertex numbers to names is easy, as we can go straight to the relevant index in the array (\( O(1) \)), but converting from names to vertex numbers requires a linear scan of the array, which is \( O(n) \). So what was once an \( O(1) \) operation (checking if an edge exists) is now an \( O(n) \) operation. We can improve the efficiency of the name to vertex number conversion by using a data structure that allows for efficient searching, such as a binary search tree.

Create a directory for this lab, change into it, and run the following command:

unzip /web/cs2521/24T1/labs/week05/downloads/files.zip

If you're working at home, download files.zip by clicking on the above link and then unzip the downloaded file.

If you've done the above correctly, you should now have the following files:

Makefile

a set of dependencies used to control compilation

Fb.c

an incomplete implementation of the Friendbook ADT

Fb.h

the interface for the Friendbook ADT

List.c

a complete implementation of the List ADT

List.h

the interface for the List ADT

Map.c

a complete implementation of the Map ADT

Map.h

the interface for the Map ADT

Queue.c

a complete implementation of the Queue ADT

Queue.h

the interface for the Queue ADT

runFb.c

a program that provides a command-line interface to the Friendbook ADT

analysis.txt

a template for you to enter your time complexity analysis

Once you've got these files, the first thing to do is to run the command

make

This will compile the initial version of the files, and produce the ./runFb executable.

File Walkthrough

runFb.c

runFb.c provides a command-line interface to the Friendbook ADT. It creates a Friendbook instance, and then accepts commands to interact with it. Here is an example session with the program once it is working correctly:

./runFb
Friendbook v1.0
Enter ? to see the list of commands.
> ?
Commands:
    + <name>             add a new person
    l                    list the names of all people
    f <name1> <name2>    friend two people
    u <name1> <name2>    unfriend two people
    s <name1> <name2>    get the friendship status of two people
    n <name>             get the number of friends a person has
    m <name1> <name2>    list all mutual friends of two people
    r <name>             get friend recommendations for a person based on mutual friends
    R <name>             get friend recommendations for a person based on friendship closeness
    ?                    show this message
    q                    quit

> + Harry
Harry was successfully added to Friendbook!
> + Ron
Ron was successfully added to Friendbook!
> + Hermione
Hermione was successfully added to Friendbook!
> f Harry Ron
Successfully friended Harry and Ron!
> f Ron Hermione
Successfully friended Ron and Hermione!
> s Harry Ron
Harry and Ron are friends.
> n Harry
Harry has 1 friend.
> n Ron
Ron has 2 friends.
> s Harry Hermione
Harry and Hermione are not friends.
> m Harry Hermione
Harry and Hermione's mutual friends:
	Ron
> r Harry
Harry's friend recommendations:
	Hermione               1 mutual friends
> u Harry Ron
Successfully unfriended Harry and Ron!
> s Harry Ron
Harry and Ron are not friends.
> q

Fb.c

Fb.c implements the Friendbook ADT. Most of the functions are complete, however, it would be helpful to read through these functions to get a good idea of how they manipulate and obtain information from the graph representation, how they create and return lists of names, and how they convert people's names to vertex numbers. You should also read the definition of struct fb and make sure you understand the purpose of each field.

List.h

List.h defines the interface to the List ADT. Some operations require a list of names to be returned to the user, and the List ADT is used for this purpose. To see how to create a list and add names to the list, you should read some of the already-completed functions in the Friendbook ADT.

Map.h

Map.h defines the interface to the Map ADT, which is used to map people's names to IDs. An important thing to note is that the Map ADT is not strictly necessary - it is only used for efficiency reasons. If we didn't have access to the Map ADT and wanted to know the ID of a particular person, we could simply scan the names array until we found the index containing that person's name, and their ID would be that index.

Queue.h

Queue.h defines the interface to the Queue ADT. The Queue ADT is currently not used.

You need to submit two files: Fb.c and analysis.txt. You must submit all of these files, even if you did not complete all of the tasks. You can submit via the command line using the give command:

give cs2521 lab05 Fb.c analysis.txt

You can also submit via give's web interface. You can submit multiple times. Only your last submission will be marked. You can check the files you have submitted here.

Most of the marks for this lab will come from automarking. To receive the rest of the marks, you must show your work to your tutor during your Week 5, 7 or 8 lab session. You will be marked based on the following criteria: