how to find type of connection between the social network entities

Question

I'm trying a social graph problem which will analyze the graph and answer the query as to what is the type of connection between the entities. By social Graph, I mean a graph which represents the friendship among the entities of the social world. The vertices are the entities and the edges are the friendship between the two entities like:

1 hop : 1st Degree

2 hop : 2nd Degree

3 hop : 3rd Degree And so on.

Here,I have 5 people Abhay, Kapil, Hari, Isha and Jaya.

Hari is friend of Kapil, Jaya and Isha.

Abhay is friend of Kapil.

Now,I want to write a function Connection(entity 1,entity2) which will return the type of connection between them.

For e.g- if I write Connection( Kapil , Isha ) ,that will return 2

similarly, Connection( Abhay , Jaya ) will return 3

If it is a disconnected graph,in case of no connection function should return 0.

I want to design Connection() funtion which will work like:- input:: Abhay Jaya output:: Degree : 3

I understand that it is an application of BFS algorithm.But unable to implement it successfully.How can I derive the C like pseudocode or the C/C++ code for this?

Answer 1

You should look at some graph algorithms to solve it. The algorithms are not language specific so you can get the ideas and implement/find implementation online.

You can solve it using 2 schemes:

1. Pre compute all the distances using algorithms like Floyd Warshall
2. Compute the distance on the fly using algorithms like Dijkstra