Challenge,how to implement an algorithm for six degree of separation?

Asked 2010-01-16T08:32:22.273

UserA-UserB-UserC-UserD-UserF

Users connected by '-' know each other.

And I need an algorithm for these 2 tasks:

Calculate the path from UserX to UserY
For UserX,calculate all users that is no more than 3 steps away.

Is there an efficient solution?

EDIT

My purpose is not to prove it right or wrong,but to calculate the result real time when necessary.

Plus,I think the most expressive way is code,even pseudo ones.

EDIT AGAIN

I've decided that this kind of job must be done inside database,so it must be a sql solution!

sql performance algorithm

Edit Report

2 Answers

The following scripts are written in sybase sql. You might have to go through minor modifications according to your db server.

Problem 1.

create table #connections (
    my_user  varchar(10)  not null  ,
    knows varchar(10)  not null  ,
        CONSTRAINT connection_pk PRIMARY KEY CLUSTERED ( my_user, knows)   
) 

create table #traversed (id varchar(10) primary key)

insert into #connections VALUES ('UserA','UserB')
insert into #connections VALUES ('UserB','UserA')
insert into #connections VALUES ('UserB','UserC')
insert into #connections VALUES ('UserC','UserB')
insert into #connections VALUES ('UserC','UserD')
insert into #connections VALUES ('UserD','UserC')
insert into #connections VALUES ('UserD','UserF')
insert into #connections VALUES ('UserF','UserD')

DECLARE @str_sql   varchar(200)               
DECLARE @str_order varchar(60)

declare @start varchar(10)
set @start = ('UserD')
declare @end varchar(10)
set @end = ('UserA')

if (@start >= @end)
    set @str_order = " order by id desc"
else
    set @str_order = " order by id asc"


INSERT INTO #traversed VALUES (@start)

WHILE (select count(*) from #traversed where id = @end) = 0    
BEGIN     
  INSERT INTO #traversed (id)    
  SELECT DISTINCT knows  
  FROM #connections e JOIN #traversed p ON p.id = e.my_user  
  WHERE e.knows NOT IN (SELECT id FROM #traversed)     
  AND e.knows between (select case when @start < @end then @start else @end end)  
      and (select case when @start < @end then @end  else @start end) 
END

set @str_sql = "SELECT #traversed.id FROM #traversed" + @str_order 
exec (@str_sql)

Problem 2.

create table #connections (
    my_user  varchar(10)  not null  ,
    knows varchar(10)  not null  ,
        CONSTRAINT connection_pk PRIMARY KEY CLUSTERED ( my_user, knows)   
) 

create table #traversed (id varchar(10) primary key)

insert into #connections VALUES ('UserA','UserB')
insert into #connections VALUES ('UserB'


                        
                        
                            answered 2010-01-21T15:28:21.880


            
            
                
                    
                        
                            
                            
                        
                        2
                        
                            
                            
                        
                        
                    
                    
                        
                        The first question can be solved using dijkstra's algorithm.
The second on using a DFS algorithm.
This has already been said by the other guys, just wanted to point out, that the most efficient solution for both problems is not available in one algorithm.

pseudocode can be found at:

[Wikipedia][1]

for dijkstra and one in python for DFS at:

http://en.wikipedia.org/wiki/Depth-first_search

                        
                        
                            answered 2010-01-16T09:05:00.457



        
        
            Your Answer