Algorithm and query for calculating 6 - degree of separation with pl/sql?

Question

I have a table called friendgraph(friend_id, friend_follower_id) and I want to calculate 6-degrees of separation for a given friend and a given degree. The table looks like this:

friend_id, friend_follower_id
    0,1
    0,9
    1,47
    1,12
    2,41
    2,66
    2,75
    3,65
    3,21
    3,4
    3,94
    4,64
    4,32

How do I go and built a query where given friend_id_a, and order_k, find the users who are k degree apart from friend_id_a?

This is how my initial query file looks like:

create or replace function degree6
 (friend_id_a in integer, order_k in integer)
return sys_refcursor as crs sys_refcursor;

I am looking for any kind of help or resources that will get me started and eventually arrive at the output.

UPDATE: The output would be a list of other friends k degrees apart from friend_id_a.

Define order-k follower B of A such that B is not A, and: 1. if k = 0, then A is the only order-0 follower of A. 2. if k = 1, then followers of A are order-1 followers of A. 3. if k > 1; then for i = 0 to k-1, B is not order-i follower of A; and B is a follower of a order-(k-1) follower of A

Thanks.

what constitutes a degree of separation? can you give an example with the provided data? — Suing, Apr 17 '15 at 04:34
for the algorithm help, check out this answered post: [here][1] [1]: http://stackoverflow.com/questions/2076715/challenge-how-to-implement-an-algorithm-for-six-degree-of-separation — Suing, Apr 17 '15 at 05:01

score 1 · Answer 1 · answered Apr 17 '15 at 08:40

1

You can build a hierarchical query and filter by level and friend_id. For example to get all friends of user 0 at level 3:

SELECT friend_id, friend_follower_id, level
FROM friends
WHERE LEVEL = 3
CONNECT BY PRIOR friend_follower_id = friend_id
START WITH friend_id = 0

answered Apr 17 '15 at 08:40

pablomatico

2,222
20
25

I am not familiar with hierarchical queries, so I don't understand what this code is doing. Is there a exit condition from this recursion? – user2512806 Apr 17 '15 at 12:48
Yes, with this query you're constructing a tree with id 0 at the root and all of the followers as children. With the CONNECT BY clause you're saying the way that parents and children are related (friend_id - follower_id), i.e, the rows with id 'friend_follower_id' are child nodes of the row with a certain 'friend_id'. LEVEL keyword tells you how far from the root you are --the degree, you were looking for-- Basically, with that query you're connecting parents and child rows with the CONNECT BY PRIOR friend_follower_id = friend_id clause. – pablomatico Apr 17 '15 at 16:48
You can find more info at: http://docs.oracle.com/cd/B19306_01/server.102/b14200/queries003.htm – pablomatico Apr 17 '15 at 16:49

score 0 · Answer 2 · answered Apr 17 '15 at 20:35

On Oracle 11gR2 or later we can use the recursive subquery-factoring syntax to do this.

with friends (id, follower, lvl) as
    ( select friend_id, friend_follower_id, 1
      from   friendgraph
      where  friend_id = 0
      union all
      select fg.friend_id, fg.friend_follower_id, f.lvl + 1
      from   friendgraph fg
             join
             friends f
             on (fg.friend_id = f.follower)
      where f.lvl + 1 <= 3
    )
select *
from   friends
/

Here's one way of implementing this in a function with a Ref Cursor:

create or replace function degree6
     (friend_id_a in integer
       , order_k in integer)
    return sys_refcursor
is
    return_value sys_refcursor;
begin
    open return_value for
        with friends (id, follower, lvl) as
        ( select friend_id, friend_follower_id, 1
          from   friendgraph
          where  friend_id = friend_id_a
          union all
          select fg.friend_id, fg.friend_follower_id, f.lvl + 1
          from   friendgraph fg
            join
              friends f
              on (fg.friend_id = f.follower)
          where f.lvl + 1 <= order_k
        )
        select *
        from   friends;
    return return_value;
end degree6;
/

Using it in SQL*Plus:

SQL> var rc refcursor
SQL> exec :rc :=  degree6(0,3)

PL/SQL procedure successfully completed.

SQL> print rc

        ID   FOLLOWER        LVL
---------- ---------- ----------
         0          1          1
         0          9          1
         1         12          2
         1         47          2

SQL>

Algorithm and query for calculating 6 - degree of separation with pl/sql?

2 Answers2