Desafío,cómo implementar un algoritmo para los seis grados de separación?

Algoritmos de gráfico puede ayudar a usted aquí. Aprender acerca de ellos también es divertido!

• Gráfico de la conectividad para la conectividad.
• Dijkstra (*) para las rutas entre los usuarios
• Simple DFS para la búsqueda de todos los usuarios de N nodos lejos de su usuario

Dijkstra o similares debe ser utilizado si usted quiere encontrar el camino más corto entre dos usuarios. Puede haber varios caminos, entre ellos, y de Dijkstra se ocupa de señalar, cuando encontró un cortocircuito en el camino de otro que se ha encontrado antes de.

Para encontrar los caminos más cortos entre todos los usuarios que usted tendrá que usar algo como Floyd-Warshall. Es un buen ejemplo de programación dinámica y es bastante simple de implementar. El pseudocódigo de la Wikipedia es:

 1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
 2    (infinity if there is none).
 3    Also assume that n is the number of vertices and edgeCost(i,i) = 0
 4 */
 5
 6 int path[][];
 7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
 8    from i to j using intermediate vertices (1..k−1).  Each path[i][j] is initialized to
 9    edgeCost(i,j) or infinity if there is no edge between i and j.
10 */
11
12 procedure FloydWarshall ()
13    for k := 1 to n
14       for i := 1 to n
15          for j := 1 to n
16             path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

Tengo una sugerencia que es muy diferente de los que ya tiene. Si usted tiene que pegarse con una base de datos SQL y no sabes nada de java esta sugerencia no servirá de mucho uso.

Que problema es específicamente un gráfico problema, así que me gustaría sugerir que, si bien el uso de una base de datos SQL para almacenar el gráfico de trabajo, un enfoque diferente sería el uso de una solución que está diseñado específicamente para los problemas de gráfico.

El Neo4j proyecto proporciona un disco basado en la base de datos en grafo, juntos en un montón de algoritmos de gráfico para trabajar con él. Cita:

Neo4j es un gráfico de la base de datos. Es un integrado, basado en disco, totalmente transaccional de persistencia Java motor que almacena los datos estructurados en los gráficos en lugar de en las mesas. Un gráfico (matemática lingo para una red) es una flexible estructura de datos que permite una gestión más ágil y rápido de estilo de desarrollo.

Un ejemplo apropiado de uso de Neo4j en su wiki muestra un grados de separación aplicación web utilizando datos de IMDB. El ejemplo ilustra la ruta más corta cálculos entre cualquier actor y Kevin Bacon.

Me gusta este ejemplo, puesto que se habla mucho sobre el modelado del dominio de su gráfico se representan. El modelado de su dominio se asegura de que usted ha pensado acerca de cosas como:

1. Dirigido vs Grafo
2. Tipos de arista/relaciones
3. Atributos tales como el borde de pesos

Como se ha mencionado en otros posts, hay una serie de algoritmos para el cálculo de corta-rutas de acceso, tales como Dijkstra, Floyd y Warshall o BFS. Todos estos han sido implementados en Neo4j y se dan algunos ejemplos aquí.

Suponiendo que la fuente de datos en una tabla: Conexiones:(PersonID, KnowsPersonID)

1) se tiene que utilizar una amplitud primera aproximación. Su potencial para el buen desempeño es limitado debido a la exponencial de la naturaleza del problema (aunque este exponencial de la naturaleza es por eso que, teóricamente, usted sólo necesita 6 grados :D). Asegúrese de limitar la profundidad de la búsqueda. Cualquiera que sea el sabor de SQL que usted elija usted probablemente va a ser mejor con su iterativo extensiones frente a un puro conjunto a partir de la solución.

El siguiente sería el enfoque básico de Microsoft de T-SQL:

CREATE PROCEDURE FindPath (@UserX int, @UserY int)

CREATE TABLE #SixDegrees(
  ConnectedUser int,
  Depth int,
  Path varchar(100),
  CONSTRAINT PK_SixDegrees PRIMARY KEY CLUSTERED (
    ConnectedUser
  )
)

DECLARE @Depth int,
        @PathFound varchar(100)
SET @Depth = 0

INSERT INTO #SixDegrees (@UserX, 0, CAST(@UserX as varchar))
/*Next line just in case X & Y are the same*/
SET @PathFound = (SELECT Path 
                  FROM #SixDegrees 
                  WHERE ConnectedUser = @UserY)

WHILE @Depth < 6 AND @PathFound IS NULL
BEGIN
  SET @Depth = @Depth + 1
  INSERT INTO #SixDegrees
  SELECT  k.KnowsPersonID, @Depth, (SELECT Path 
                                    FROM #SixDegrees 
                                    WHERE ConnectedUser = k.Link) + ',' + CAST(k.KnowsPersonID AS varchar)
  FROM (
      SELECT  MIN(ConnectedUser) Link, KnowsPersonID
      FROM    #SixDegrees
              JOIN Connections ON
                PersonID = ConnectedUser
      WHERE   Depth = @Depth
              /*EDIT: Added the following*/
              AND KnowsPersonID NOT IN (
                  SELECT  ConnectedUser
                  FROM    #SixDegrees
                  )
      GROUP BY KnowsPersonID
      ) k

  SET @PathFound = (SELECT Path 
                    FROM #SixDegrees 
                    WHERE ConnectedUser = @UserY)
END

IF @Path IS NULL
  PRINT 'No path found'
ELSE
  PRINT @Path
GO

EDIT: En la solución anterior, originalmente me olvidé de excluir a los usuarios que ya están en el #SixDegrees de la tabla temporal.

2) Un pequeño arreglo en la de arriba para siempre bucle a una profundidad de 3 que le dejaría con #SixDegrees que contiene todos los Usuarios que están interesados en.

Sin embargo, los siguientes puro establece en función de la solución debe ser más eficiente:

SELECT  DISTINCT KnowsPersonID
FROM    Connections
WHERE   PersonID IN (
    SELECT  DISTINCT KnowsPersonID
    FROM    Connections
    WHERE   PersonID IN (
        SELECT  KnowsPersonID
        FROM    Connections
        WHERE   PersonID = @UserX
        ) l1
    ) l2

Las siguientes secuencias de comandos se escriben en sybase sql. Usted podría tener que ir a través de pequeñas modificaciones de acuerdo a su servidor de db.

Problema 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)

Problema 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','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 @start varchar(10)
set @start = ('UserB')

declare @higher_counter int
declare @lower_counter int

set @higher_counter = 0
set @lower_counter = 0

INSERT INTO #traversed VALUES (@start)

WHILE (@higher_counter < 3)
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 > @start 

  set @higher_counter = @higher_counter +1
END  

WHILE (@lower_counter < 3)
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 < @start 

  set @lower_counter = @lower_counter +1
END   

SELECT #traversed.id FROM #traversed