Connection between two users

Question

I run my own website where people have the ability to have friends. This is how I store friendships:

id1 | id2
 1  |  2
 1  |  3
 2  |  4

Basically user id 1 is friends with user id 2 and id 3 and user 2 is friends user id 4.

What I'm trying to get is how, for example, are 1 and 4 connected. Currently it's like that:

1 -> 2 -> 4

If it's about between 4 and 3 it would be:

4 -> 2 -> 1 -> 3

The idea is to find as quick link between those two as possible

The only way I can think about is creating a massive big loop with a lots of loops and stuff like that which probably can be better and more efficient.

Answer 1

RDBMS is not good at doing stuff like this.

What you need is a graph db, and I strongly recommend Neo4j, which is popular and open sourced.

Answer 2

Shortest friendship path is usually found by using an algorithm called two-way search. Thw main idea is to look at network of friendships as an undirected graph, where you are seeking the shortest path between 2 nodes. This mentioned algorithm starts searching from both nodes at the same time, discover neighbour nodes of the already known ones. When the two surfaces of known nodes first overlap, than a the shortest path is found.

Please note that certain special cases needed to be handled, such as when one of the people is in an "island" at the graph, such a node set that is not connected to other nodes (think of a community with no relationship to thw outside world)

Bottom line it is a not-so-big while loop.