CODEWITHSUNDEEP
phpmysqlsqlalgorithm
Marius S
Marius S

Reputation: 287

Determine if two users are connected via friends of friends

So there is a friendship_request table:

+--------+----------+
| sender | receiver |
+--------+----------+
|      1 |        2 |
|      2 |        1 |
+--------+----------+

Two users are friends if both have sent each other a request.

I'm using PHP's array_intersect with arrays containing all the friends of each user to determine if they are connected through friends of friends.

i.e. 

1 <--> 2 <--> 3

What is the most efficient way to find if two users have friends that have friends that are friends with each other. i.e. 

+--------+----------+
| sender | receiver |
+--------+----------+
|      1 |        2 |
|      2 |        1 |
|      2 |        3 |
|      3 |        2 |
|      3 |        4 |
|      4 |        3 |
+--------+----------+


1 <--> 2 <--> 3 <--> 4

User 1 should know of his relationship with User 4.

PS: It's ok with PHP/pseudocode or MySQL

Edit: I do not want to create another table or views. I want to get the best solution using the resources described above.

Upvotes: 0

Views: 166

Answers (2)

Eugene Bartosh
Eugene Bartosh

Reputation: 324

first create view detecting friendships: 

CREATE VIEW friendship (friend1, friend2) 
AS SELECT p1.id, p2.id from person as p1, person as p2
WHERE 
(SELECT count(*) from friendship_request as fr1 WHERE 
fr1.sender = p1.id AND fr1.receiver = p2.id) > 0 
AND 
(SELECT count(*) from friendship_request as fr2 WHERE 
fr2.receiver = p1.id AND fr1.sender = p2.id) > 0

now query for 1st level connections is as simple as

SELECT p1.name, p1st.name, p2.name 
FROM person as p1, person as p2, person as p1st, 
friendship as fs1, friendship as fs2 
WHERE p1.id = fs1.friend1 
AND p2.id = fs2.friend1 
AND fs1.frind2 = fs2.frind2 
AND fs2.frind2 = p1st.id

for 2nd level connections:

SELECT DISTINCT p1.name, p2nd1.name, p2nd2.name, p2.name 
FROM person as p1, person as p2, person as p2nd1, person as p2nd2, 
friendship as fs1, friendship as fs2, friendship as fs2nd
WHERE  p1.id = fs1.friend1 
AND p2.id = fs2.friend1 
AND fs1.frind2 = fs2nd.frind2 
AND fs2.frind2 = fs2nd.frinend2 
AND p2nd1.id = fs1.frind2 
AND p2nd2.id = fs2.frind2

And so on.

Did not test but in any normal RDBMS should work :-)

Upvotes: 1

HDev
HDev

Reputation: 39

I would create a graph structure. An Adjacency List representation would work well. Then you can just run depth first search.

Upvotes: 0

Related Questions