CSE 2010, HW6

Due Tue Apr 9 at the start of your lab section; Submit
Server: class = cse2010, assignment = hw6SxIndividual
Due Tue Apr 9 at the end of your lab section; Submit Server:
class = cse2010, assignment = hw6SxGroupHelp
x is 14, 23, or j—your merged section number (j for java).
When a user searches for a person (“target”) on an online
social network, the user might want to be a friend of the target, but the user is not currently a friend of the target. For
example, a user would like Donald Trump to be his/her friend,
but the user is not a friend of Donald Trump. How would you
design a system to help the user?
HW6 explores graph algorithms that can help the user finds
mutual friends or “intermediate” friends of the user and the
target. A mutual friend is someone who is both a friend of the
user and the target. For example, if areFriends(user, Mickey)
and areFriends(Mickey, target), Mickey is a mutual friend. An
intermediate friend is someone who is a friend of the user and
is indirectly connected to the target in the social network. For
example, if areFriends(user, Mickey), areFriends(Mickey, x),
areFriends(x, y), ..., and areFriends(z, target), Mickey is an
intermediate friend. Naturally, we also desire the intermediate
friend who is closet to the target. The user can ask the mutual or intermediate friend to introduce the user to the target.
Moreover, users can add friendships :-) and remove friendships
:-(.
To find mutual or intermediate friends, we can use the
breadth-first search algorithm. The algorithm allows us to
find the shortest path from the user to the target. If the path
is of length 2, a mutual friend exists. If the path length is more
than 2, an intermediate friend exists. Note that multiple paths
of the same length might exist and a path might not exist at
all. If at least one shortest path exists, the system will report
the shortest path(s) and the mutual/intermediate friend(s).
Friends (adjacent vertices) are visited in alphabetical order (to produce unique output for easier testing/debugging).
We will be evaluating your submission on code01.fit.edu; we
strongly recommend you to ensure that your submission functions properly on code01.fit.edu.
Extra Credit 1 (10 points) Separate submission via
hw6extra1.c (or HW6Extra1.java). Similar to regular credit,
except if ties exist, multiple shortest paths are reported (in the
order when adjacent vertices are visited alphabetically).
Extra Credit 2 (10 points) Separate submission via
hw6extra2.c (or HW6Extra2.java). Not all friendships are
equally close. Closer friendships are more desirable in finding the target. To estimate how close a friendship is, we can
measure the frequency of communication (e.g. texts, email,
calls, ...) between two users. Frequency of communication in
HW6 is the average number of days between two successive
communications and is an integer (for simplicity). Using Dijkstra’s shortest path algorithm, we can find the mutual or
intermediate friend on the shortest path from the user to the
target. Similar to regular credit, report the first shortest path
found—adjacent vertices are visited alphabetically.
Extra Credit 3 (10 points) Separate submission via
hw6extra3.c (or HW6Extra3.java). Similar to Extra Credit
1, except if ties exist, multiple shortest paths are reported (in
the order when adjacent vertices are visited alphabetically).
Input: Command-line argument for hw6.c (HW6.java) [and
Extra Credit] is:
• filename of initial friendships—the first line has the number of users, each of the following lines has two users who
are friends (followed by frequency of communcation for
Extra Credits 2 and 3)
• filename of actions—possible actions (each on one line)
are:
– AddFriendship user1 user2 [frequency in Extra
Credits 2 and 3]
– RemoveFriendship user1 user2
– WantToBefriend user target
For simplicity, all the users are in the initial friendships and
the number of users does not change during the actions. Assume users are valid in the actions.
Output: Output goes to the standard output (screen):
1. AddFriendship user1 user2 (frequency in Extra Credit)
[ExistingF riendshipError]
2. RemoveFriendship user1 user2 [NoF riendshipError]
3. WantToBefriend user target [AlreadyAF riendError]
- Length of the shortest path: k
- Your mutual/intermediate friend is x.
- Path: user x y ... z target
or
- Sorry, none of your friends can help introduce you to
target.
Extra Credit 1: Only WantToBefriend is different with
possibly additional mutual/intermediate friends and paths.
The following 2 lines are repeated for each additional mutual/intermediate friend:
- Your mutual/intermediate friend is x.
- Path: user x y ... z target
Extra Credits 2 and 3: Same as the corresponding output
for Regular Credit and Extra Credit 1.
Sample intput and output files are on the course website.
Submission: Submit hw6.c (HW6.java) that has the main
method and other program files. Submissions for Individual
and GroupHelp have the same guidelines as HW1.
For Extra Credits, submit hw6extra1.c, hw6extra2.c, and/or
hw6extra3.c (or HW6Extra1.java, HW6Extra2.java, and/or
HW6extra3.java) that have the main method and other program files. GroupHelp and late submissions are not applicable.
Note the late penalty on the syllabus if you submit after the
due date and time as specified at the top of the assignment.
1