Menu
I'm building a network analysis using D3.js to show connected phone numbers within my app down to six degrees of separation. The SQL (postgres) to find initial connections is below and fairly straightforward. However, I am stumped on how to modify this to traverse through six levels of connections then stop.
SELECT player_id, ps.player_state, ps.email, ph.create_date
FROM game.phone_hashes ph
INNER JOIN game.customer_settings cs ON cs.id = ph.player_id
WHERE hash IN (SELECT hash FROM game.phone_hashes WHERE player_id = $1);
I have found mentions of Common Table Expressions (CTE) and recursion through research into this problem, but am unsure how to apply them here.
What I'm aiming for is to get all the players connected to the initial player ($1) through a common phone hash, then all the players connected to each of those connections through a common phone hash, and on and on out to 6 degrees of separation.
651
The fastest O(n) algorithm for six-degrees of separation would probably be finding the sets of all users 1-step away from UserX and UserY, and finding the intersection of those two sets. If none, then add the users 2-steps from UserX and intersect; then add users 2-steps from UserY and intersect; etc. up to 3.
Six degrees of separation is the theory that any person on the planet can be connected to any other person on the planet through a chain of acquaintances that has no more than five intermediaries.
SQL Query mainly works in three phases . 1) Row filtering - Phase 1: Row filtering - phase 1 are done by FROM, WHERE , GROUP BY , HAVING clause. 2) Column filtering: Columns are filtered by SELECT clause. 3) Row filtering - Phase 2: Row filtering - phase 2 are done by DISTINCT , ORDER BY , LIMIT clause.
The huge volumes of data collected by the game allowed sociology researchers to analyse exactly how interconnected Hollywood actors really are, and they found that six degrees of separation does indeed appear to exist, but it's people's random acquaintances, not their friends, that are the key to all of this.
I think this is what you meant:
with recursive tc as(
select $1 as player_id, 1 as level
union
select ph2.player_id, level+1
from tc, phone_hashes ph1, phone_hashes ph2
where tc.player_id=ph1.player_id
and ph1.hash=ph2.hash
and tc.level < 6
)
select distinct player_id from tc
Think it would be:
-- 6 degrees of separation
SELECT player_id, ps.player_state, ps.email, ph.create_date
FROM game.phone_hashes ph
INNER JOIN game.customer_settings cs ON cs.id = ph.player_id
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE player_id = $1))))));
Please see workings below:
-- 1 degree of separation
SELECT player_id, ps.player_state, ps.email, ph.create_date
FROM game.phone_hashes ph
INNER JOIN game.customer_settings cs ON cs.id = ph.player_id
WHERE hash IN
(SELECT hash FROM game.phone_hashes WHERE player_id = $1);
-- 2 degrees of separation
SELECT player_id, ps.player_state, ps.email, ph.create_date
FROM game.phone_hashes ph
INNER JOIN game.customer_settings cs ON cs.id = ph.player_id
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE player_id = $1));
-- 3 degrees of separation
SELECT player_id, ps.player_state, ps.email, ph.create_date
FROM game.phone_hashes ph
INNER JOIN game.customer_settings cs ON cs.id = ph.player_id
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE player_id = $1)));
-- 4 degrees of separation
SELECT player_id, ps.player_state, ps.email, ph.create_date
FROM game.phone_hashes ph
INNER JOIN game.customer_settings cs ON cs.id = ph.player_id
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE player_id = $1))));
-- 5 degrees of separation
SELECT player_id, ps.player_state, ps.email, ph.create_date
FROM game.phone_hashes ph
INNER JOIN game.customer_settings cs ON cs.id = ph.player_id
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE player_id = $1)))));
-- 6 degrees of separation
SELECT player_id, ps.player_state, ps.email, ph.create_date
FROM game.phone_hashes ph
INNER JOIN game.customer_settings cs ON cs.id = ph.player_id
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE hash IN
(SELECT hash FROM game.phone_hashes
WHERE player_id = $1))))));
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
