Faculty of Computer Science and Engineering
Department of Computer Science
LAB SESSION 6
Faceline – A Social Network
1. OBJECTIVE
The objectives of Lab 5 are (1) to introduce an implementation of directed graph and (2)
to practice some basic algorithms to handle a graph
2. INTRODUCTION
Faceline is a social network developed by a group of BKIT students. The social
membership was initially limited by the founders to CSE students, but was expanded to
other students in the university.
Figure 1 illustrates a social network formed in Faceline. There are three users: A, B and
C. Users A, B and C have posted 10,7 and 2 status in their Walls, respectively. User A
and B are friends. A has sent 5 messages to B and B also has sent 4 messages back to A.
Meanwhile, A is a follower of C. A has sent 2 message to C, but C has never replied
because she has no interests on A.
Figure 1 – A social network in Faceline
Required Exercises
1. Suggest a suitable data structure to represent Faceline.
2. Define and implement the following methods for the data structures
defined in Question 1:
- join (A): User A joins the network
- post (A): User A has just updated one more status in his Wall.
1/2
Faculty of Computer Science and Engineering
Department of Computer Science
- makefriend (A,B): A and B become friends
- follow(A,C): A becomes a follower of C in the network.
- send(A,B): A sends a message to B (supposed that at the
moment A is a friend or a follower of B)
3. Define and implement the method find_contact(B,C): B wants to
make contact with C but B has no connection to C. This method returns
a lists of suitable members X who can introduce B to C. X must be
friend of B and a friend or a follower of C. For example, in Figure 1,
when called find_contact(B,C), the methods will result in {A}.
Advanced Exercises
4. Define and implement the method has_connection(A,B) if user A and
user B could be friend according to Faceline network.
5. Propose an additional data structure and some supplementary
methods in order to manage all messages published by users. Other
users could access if they have connection together. Each message is
stored in a separated file using following context to rename:
Username_Date_msgNumber, for example: “na_120904_1.txt”
contains the first message send by user ‘na’on 04 Sept 2012.
2/2
