Conexão entre dois usuários

9

Eu gerencio meu próprio site onde as pessoas têm a capacidade de ter amigos. É assim que eu armazeno amizades:

id1 | id2
 1  |  2
 1  |  3
 2  |  4

Basicamente, o id do usuário 1 é amigo do id do usuário 2 e id 3 e o usuário 2 é o id do usuário 4 do seu amigo.

O que estou tentando obter é como, por exemplo, são 1 e 4 conectados. Atualmente é assim:

1 -> 2 -> 4

Se é entre 4 e 3, seria:

4 -> 2 -> 1 -> 3

A ideia é encontrar um link rápido entre os dois possíveis

A única maneira que posso pensar é criar um grande loop com muitos loops e coisas do tipo que provavelmente podem ser melhores e mais eficientes.

    
por Nikola 12.03.2013 в 18:06
fonte

5 respostas

1

O caminho de amizade mais curto geralmente é encontrado usando um algoritmo chamado pesquisa bidirecional. A idéia principal é olhar para a rede de amizades como um grafo não direcionado, onde você está procurando o caminho mais curto entre dois nós. Este algoritmo mencionado inicia a busca de ambos os nós ao mesmo tempo, descobre os nós vizinhos dos já conhecidos. Quando as duas superfícies de nós conhecidos se sobrepõem pela primeira vez, é encontrado um caminho mais curto.

Por favor, note que certos casos especiais precisam ser tratados, como quando uma das pessoas está em uma "ilha" no gráfico, como um conjunto de nós que não está conectado a outros nós (pense em uma comunidade sem relacionamento) para fora do mundo)

Linha de fundo é um loop não tão grande.

    
por sw0rdf1sh 12.03.2013 / 19:45
fonte
3

O RDBMS não é bom em fazer coisas assim.

O que você precisa é de um banco de dados , e eu recomendo fortemente Neo4j , que é popular e de código aberto.

    
por adamsmith 09.08.2013 / 05:23
fonte
1

O que eu tentaria primeiro é uma pesquisa inicial.

Observe que o código a seguir não funcionará sem modificações, porque nem chequei os erros de sintaxe. A função query () deve retornar uma lista de entradas como você vê. Pretende dar uma ideia.

/* Return one of the shortest friendship paths from f1 to f2. Returns false when
 * path is longer than limit or no path exists. 
 * PROTOTYPE FIX IT YOURSELF
 */
function friend_path($f1, $f2, $limit) {
    $friended = array($f1 => false); // The tree of friendships leading to f1
    $discovered_friends = array($f1); // List of friends to examine next
    while($limit-- > 0) {
        $interesting_friends = $discovered_friends;
        $discovered_friends = array();
        foreach(query("
            SELECT id1 AS friender, id2 AS friendee  
            FROM friendships 
            WHERE id1 in (".join(',', $interesting_friends).")
            ") as $discovered_link
        ) {
            $friendee = $discovered_link['friendee'];
            $friender = $discovered_link['friender'];
            if (!isset($friended[$friendee])) {
                $discovered_friends []= $friendee;
                $friended[$friendee] = $friender;
                if ($friendee == $f2) {
                    return friend_path_track($friended, $friendee, $track);
                }
            }
        }
        if (count($discovered_friends) < 1) return false;
    }
    return false;
}

function friend_path_track($friended, $friendee, $track) {
    $track []= $friendee;
    if ($friended[$friendee]) === false) return array_reverse($track);
    return friend_path_track($friended, $friended[$friendee], $track);
}

Este código foi otimizado para simplificar. Para qualquer coisa além de bancos de dados de brinquedo, você deve fazer uma pesquisa bidirecional onde você mantém duas listas, friended e friends (a árvore de frienders para f2). Você estenderia a lista que é mais curta, enquanto procura uma correspondência na outra lista. Você não pode enganar a complexidade, então você terá que manter o limite de iterações muito baixo, você gosta do som dos servidores de lixo.

    
por sba 09.08.2013 / 13:02
fonte
0

É melhor fazer uma pesquisa inicial em ambas as direções, ou seja, de ambos os indivíduos em questão e interromper esse processo quando você encontrar uma conexão ou atingir o limite de profundidade especificado. A ideia também é alcançar os indivíduos mais populares primeiro (enquanto realiza BFS)

    
por user_19 09.08.2013 / 05:13
fonte
0

Isso seria com bordas com peso de 1. Há um código de exemplo para calcular a conexão entre 2 amigos em uma rede social no PHP

    
por kb0000 31.12.2013 / 09:49
fonte