Graph Friendship

In this exercise you are invited to implement a program that suggests new friends to Social Networks.

1 Entrance

Entering your program will be a non-directed G (V, E) graph representing friendships on a social network. The input file will be a text file to contain one edge per line. Below is a small example:

# Undirected graph
# fromNodeId ToNodeId
0 1
1 2
2 3
4 1
1 3
5 6
7 6

In the input file lines starting with # are comments. Each other line contains an edge, which is represented by the node identifiers. The above example is shown in chart format below: see image.

2 Graph Representation

You can use any of the representations we have learned in the lesson. This means an adjacency matrix, a CSR, or an adjacency list. After opening the input file, be sure to load the graph in memory.

3 Friends of Friends

Your implementation should consider friends of friends and suggest them as new friendships.

Example 1 Node 0 is friends with node 1. Node 1 is friends with nodes 0, 2, 3 and 4. So in the case of 0 he should be suggested to potential friends 2, 3 and 4.

Example 2 Node 4 is friends with node 1. Node 1 is friends with nodes 0, 2, 3 and 4. So in the case of 4 he should be suggested to potential friends 0, 2 and 3.

In other words, for each node v of the graph, you must find the set of nodes you can to reach using two edges.

4 Exit

The output of your program should be couples with possible friendships. Below is the output for the example of the figure:

0 2
0 3
0 4
2 0
2 4
3 0
3 4
4 0
4 2
4 3
5 7
7 5

Be aware that many potential friendships often occur through different nodes. Not you need to do something about it such as removing duplicates.