Objectives
To explore an application of graphs
To get some practice with graph problems
To perform complAssignment Project Exam Helpexity analysis on graph algorithms
To implement some basic features of social networks
Demo in the Week 5, 7 or 8 lab session
Submit see the Submission section
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 aCOMPllows for2521 many 24reaTl-worl2 d 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 acount 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:
. 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.
. 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? COMP2521 24T2
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, converting from a name to a vertex number adds quite a bit of overhead to our graph operations. Converting from a vertex number to a name is easy, as we can go straight to that index in the array (O(1)), but converting from a name to a vertex number requires a linear scan of the array, which is
O(n). COMP2521 24T2
We can improve the efficiency of the name to vertex
number conversion by using a data structure that allows for efficient searching, such as an ordered array. Friendbook uses a Map ADT to map names to vertex numbers and efficiently find the vertex number associated with a particular name (see the nameToId function in Fb.c). Since the Map ADT is implemented using an ordered array, this lookup can be achieved in O(logn) time.
:
Setting Up
Create a directory for this lab, change into it, and run the following command:
$ unzip /web/cs2521/24T2/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
COMP2521 24T2
tests/ a subdirectory that contains inputs for some basic tests ca ses
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 aAssignment Project Exam Help 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!COMP2521 24T2
> + 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 HermioneAssignment Project Exam Help
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 ListCOMP ADT is 2521used f or24 thiTs2 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 defines theAssignment Project Exam Help interface to the Queue ADT. The
Queue ADT is currently
Queue.h
not used, but should be used in the optional task if you decide to do it.
Task 1 – Friending 🙂
Implement the FbFriend() function in Fb.c, which takes the names of two people, and friends them if they are not already friends. The function should return true if the people were not friends and were successfully friended, and false if the two people were already friends.
You should implement your function so that the adjacency lists are kept in ascending order. For example, in the example in the Background section, since Harry (0) is friends with Ron (1) and Hermione (2), 1 should appear before 2 in Harry’s adjacency
list.
You can assume that the two people exist and are not the same person.
We have provided a function newAdjNode which creates a new adjacency list node. COMP2521 24T2
HINT:
Is inserting into an adjacency list similar to a problem that you have solved in a previous lab exercise?
Once you think you’ve got the function working, test it by recompiling with make and running the runFb program. You can test whether your function
:
works using the + (add person), f (friend) and s (friendship status) commands. For example:
$ ./runFb
Friendbook v1.0
Enter ? to see the list of commands.
> + Harry
Harry was successfully added to Friendbook!
> + Ron
Ron was successfully added to Friendbook!
> + Hermione
Hermione was successfully added to Friendbook!
> s Ron Hermione
Ron and Hermione are not friends.
> f Ron Hermione
Successfully friended Ron and Hermione!
> s Ron Hermione
Ron and Hermione are friends.
> s Harry Ron
Harry and Ron are not friends.
> f Harry Ron
Successfully friended Harry and Ron!
> s Harry Ron
Harry and Ron are friends.
> s Ron Hermione
Ron and Hermione are friends.
> s Harry Hermione
Harry and Hermione are not friends. COMP2521 24T2
You can run the abov e test case with the following command:
$ ./runFb -e < tests/friend-1.txt
This command runs the ./runFb program and causes it to read Friendbook commands from the file tests/friend-1.txt. The -e option (which stands for “echo”) causes the program to print out the commands to the terminal as they are being run, which makes it easy to see which operations are being performed.
When you’re certain that the function works correctly, determine its worst case time complexity and write in analysis.txt along with an explanation. The time complexity shoulAssignment Project Exam Helpd be in terms of n, where n is the total number of people.
Task 2 – Counting Friends
Implement the FbNumFriends() function in Fb.c, which takes the name of a person and returns the number of friends they have. You can assume that the person exists.
Once you think you’ve got the function working, test it by recompiling with make and running the runFb program. Here is an example test case:
$ ./runFb
Friendbook v1.0 Enter ? to see the list of commands.
> + 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!COMP2521
1 friend.
> n Ron
Ron has 2 friends.
> n Hermione
Hermione has 1 friend.
The Friendbook commands used in this example have been stored in the file tests/num-friends-1.txt, so you can also run this test case with the following command:
:
$ ./runFb -e < tests/num-friends-1.txt
When you’re certainAssignment Project Exam Help that the function works correctly, determine its worst case time complexity and write in analysis.txt along with an explanation. The time complexity should be in terms of n, where n is the total number of people.
Task 3 – Fin.comding Mutual Friends
Implement the FbMutualFriends() function in Fb.c, which takes the names of two people, and returns a list of all their mutual friends. A person is a mutual friend of two people if that person is friends with both of those people.
To illustrate this, here is an example:
In the example, Harry and Hermione have three mutual friends: Neville, Ron and Luna. Draco and Vincent have one mutuaCOMPl friend:2521 Gregory 24. HTa2rry and
Draco have no mutual friends.
HINT:
To find out how to create a list and add names to it, see the comments in List.h, or read one of the existing functions in Fb.c that use the List
ADT. :
Once you think you’vAssignment Project Exam Helpe got the function working, test it by recompiling with make and running the runFb program. You can run the following command to test the scenario given above: $ ./runFb -e < tests/mutual-friends-1.txt
When you’re certain that the function works correctly, determine its worst case time complexity and write in analysis.txt along with an explanation.
The time complexity should be in terms of n, where n is the total number of people.
Implement the FbUnfriend() function in Fb.c, which takes the names of two people, and unfriends them if they are friends. The function should return true if the people were friends and were successfully unfriended, and false if the two people were not friends (and so they could not be unfriended). You can assume that the two people exist and are not the same person.
Once you think you’ve got the function working, test it by recompiling with make and running the runFb program. Here is an example test case: $ ./runFb
Friendbook v1.0 COMP2521
Enter ? to see the list of commands.
> + 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.
> s Ron Hermione
Ron and Hermione are friends.
> u Harry Ron
Successfully unfriended Harry and Ron!
> s Harry Ron
Harry and Ron are not friends.
> s Ron Hermione
Ron and Hermione are friends.
> n Harry
Harry has 0 friends.
The Friendbook commands used in this example have been stored in the file tests/unfriend-1.txt, so you can also run this test case with the following command:
$ ./runFb -e < tests/unfriend-1.txt
Task 5 – Generating Friend
RCOMPecomm2521e
24ndaT2tions
Implement the FbFriendRecs1() function in Fb.c, which takes the name of a person and finds friend recommendations for them. The function should store the recommendations for them in the given recs array and return the number of recommendations stored in the array.
The function should only recommend people who are friends of friends of the person. In other words, it should only recommend people who share at least one mutual friend with the person. Obviously, it should not recommend someone who is already the person’s friend.
Each recommendation consists of the name of the person being
recommended and tAssignment Project Exam Helphe number of mutual friends they share with the given person.
The recommendationsEmail: should be sorted in descending order on the number of mutual friends shared, since someone with more mutual friends is more likely to be known by the person, and is therefore more likely to be added as a friend.
For example, consider the following scenario:
If FbFriendRecs1() is called with the name “Harry”, the following output should be produced:
Harry’s friend recommendations:
Neville 3 mutual friends
Lavender 2 mutual friends
Draco 1 mutual friendsCOMP2521
Explanation: Neville should be recommended first as he shares three mutual friends with Harry: Luna, Ron and Hermione. Lavender should be recommended next as she shares two mutual friends with Harry: Ron and Hermione. Draco should be recommended last as he shares just one mutual friend with Harry: Hermione. (Note: There is no typo on the last line – it is left as “friends” for simplicity’s sake.)
Once you think you’ve got the function working, test it by recompiling with make and running the runFb program. You can run the following command to test the scenario given above: $ ./runFb -e < tests/friend-recs-
1.txt
When you’re certain that the function works correctly, determine its worst case time complexity andEmail: write in analysis.txt along with an explanation. The time complexity should be in terms of n, where n is the total number of people.
Implement the FbFriendRecs2() function in Fb.c, which takes the name of a person and finds friend recommendations for them. The function should return a list containing the names of all the people being recommended, with the names being ordered as described below.
Unlike FbFriendRecs1, this function should recommend all people who are reachable from the given person via friendship links (not just people who share a mutual friend), and should recommend people who are “closer” to the person first. In other words, friends of friends of the person should be recommended first, then friends of friends of friends, and soCOMP on. Obv2521iously, 24it shToul2 d not recommend someone who is already the person’s friend. If multiple people are the same “distance” from the person, they can be recommended in any order.
Limit the number of recommendations to 20 to avoid generating too many recommendations.
For example, consider the same scenario as in Part 2:
:
If FbFriendRecs2() was called with the name “Luna”, the following is one possible valid output:
Luna’s friend recommendations:
Ron
Hermione
Draco
Lavender
Vincent
Gregory
Explanation: Ron and Hermione are the closest people to Luna who are not also her friends, so they are recommended first. The example output recommends Ron first and then Hermione, but it would be equally valid to recommend Hermione first and then Ron. Draco and Lavender are the next furthest away, so they are recommended next. It would be valid to recommend Lavender before Draco. Vincent and Gregory are the next furthest away, so they are printed next. Once again, it would be valid to recommend Gregory before Vincent.
When you think you are done, use the make command to recompile the runFb program and then develop some scenCOMParios to2521 test your 24 cTo2de. HINT:
You will need to use a graph traversal algorithm to complete this task. But which one? You can review the graph traversal algorithms here, and then follow the pseudocode of your chosen algorithm.
: SubmissionAssignment Project Exam Help
You need to submit twoEmail: 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.
After you submit, you must check that your submission was successful by going to your submissions page. Check that the timestamp is correct. If your
submission does not appear under Last Submission or the timestamp is not correct, then resubmit.
Assessment COMP2521 24T2
Code correctness 4 Your code for each task will be automarked.
Automarking will be run after submissions have
is
run you will be able to view your results here.
Complexity analysis 1 A
E ssignment Project Exam HelpThis
mark is based on how accurate you were with
your time complexity analysis and the quality of your
explanations in
COMP2521 24T2: Data Structures and Algorithms is brought to you by the
For all enquiries, please email the class account at [email protected]
CRICOS Provider 00098G
