Friends of Friends

Facebook is a major social networking tool. It utilizes many mathematical/computer science algorithms, such as the "degree of separation" problem. It was once believed that everyone was connected by 6 degrees of separation. Facebook statistics have reduced that to 3.74 as of November 2011. http://www.guardian.co.uk/commentisfree/2011/nov/23/facebook-degrees-of-separation . More recently, Microsoft thinks it's actually 6.6 degrees: Proof! Just six degrees of separation between us.

The degree of separation between two people is the shortest path that connects them through their friendships. For example, in the diagram below, there are many different paths between Abby and Alberto. Some of these paths are:

Abby -> Zoey -> Alberto

Abby -> Natalie -> Zoey -> Alberto

Abby -> George -> Ali -> Kara -> Ricardo -> Jeff -> Alberto

The shortest path between Abby and Alberto has two steps (Abby -> Zoey, and Zoey -> Alberto), so we say the degree of separation is 2. Additionally, Alberto would be a friend of a friend of Abby.

Input/Output

Your program will have 6 commands described below. There is no need for error checking. Assume that x and y are integers, x != y, 1 <= x <= 50 && 1 <= y <= 50. Also assume that each command (i,d,n,f,s,q) occurs one per line and that each is followed by the correct number of parameters (0, 1 or 2), on the same line, each separated by 1 space.

i x y - make person x and person y friends. If they are already friends, no change needs to be made. If either x or y is a new person, add them.

d x y - delete the friendship between person x and person y.

n x - output the number of friends that person x has.

f x - output the number of "friends of friends" that person x has. Notice that x and direct friends of x are not counted as "friends of friends."

s x y - output the degree of separation between x and y. If there is no path from x to y, output "Not connected".

q - quit the program.

Sample Input

i 20 10
i 20 9
n 20
f 20
s 20 6
q

Sample Output

2
3
4

Why?

n 20: Person 20 has two friends (10 and 9)
f 20: The friends of friends of 20 are 8, 11, 12.
s 20 6: The shortest path is 20 -> 9 -> 8 -> 7 -> 6.

Things you need to know:

1. Represent the matrix of relationships between people using a two dimensional integer array called friendships Make this array global to the class.

   Learn more about 2-D arrays here

   http://www.roseindia.net/java/beginners/arrayexamples/two.shtml

   If people 5 and 20 are friends, the array will contain a 1 at friendships[5][20] and at friendships[20][5]. Otherwise it contains a 0. To represent the friendships of people 1-6 above, the matrix would look like this:

   Index	1	2	3	4	5	6
   1	0	0	0	0	0	1
   2	0	0	0	0	0	1
   3	0	0	0	1	1	1
   4	0	0	1	0	1	1
   5	0	0	1	1	0	1
   6	1	1	1	1	1	0

   
   
   
2. To calculate the degrees of separation use the Floyd-Warshall algorithm.

   Here is the pseudcode for the algorithm (modified from Wikipedia).

    1  int path[][];
    2 /* This algorithm generates a 2-dimensional array that stores the degree of   separation between any two people. 
         At each step in the algorithm, path[i][j] is the length of the shortest path
    3    from i to j using intermediate friends (1..k-1).   
         Initialize the path array so that each path[i][j] is 
    4    1 if two people are friends or infinity (that is, a very large number) if there is no relationship.
    5 */
    6
    7 method FloydWarshall ()
    8    for k = 1 to n
    9       for i = 1 to n
   10          for j = 1 to n
   11             path[i][j] = min ( path[i][j], path[i][k] + path[k][j] );
   

   Note: path starts out as a current copy of the actual friendships array with 1's copied over as is, and "infinity" copied over where there were 0's. After the FW shortest path algorithm is run on path, it will contain the degree of separation between any two connected people, and "infinity" where two people are not connected.

   Read more about this and see the PHP code for the algorithm here http://www.microshell.com/programming/php/computing-degrees-of-separation-in-social-networki ;ajfk;lsajfng/2/

3. To calculate friends of friends, you can use the 2D array generated by the Floyd-Warshall algorithm. Just note that anyone who is a "friend of friend" of person x has a degree of separation of 2.

How to Approach a Larger Problem Like This One:

1. flow chart it
2. break it down into smaller problems: make a list of functionality you need to implement, this might include a list of methods you need to write.
write and test one component at a time

Assessment (/47)