Connessione tra due utenti

Question

Gestisco il mio sito Web in cui le persone hanno la possibilità di avere amici. Questo è come devo conservare le amicizie:

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

Fondamentalmente id utente 1 è diventato amico di user id 2 e ID 3 e l'utente 2 è amici id utente 4.

Quello che sto cercando di ottenere è come , ad esempio, sono 1 e 4 collegati. Attualmente è così:

1 -> 2 -> 4 

Se si tratta di tra il 4 e 3 sarebbe:

4 -> 2 -> 1 -> 3 

L'idea è quella di trovare il più velocemente legame tra quei due possibile

L'unico modo Posso pensare a creare un grande ciclo enorme con un sacco di loop e cose del genere che probabilmente possono essere migliori e più efficienti.

Answer 1

Il percorso di amicizia più breve si trova in genere utilizzando un algoritmo chiamato ricerca bidirezionale. L'idea principale è quella di guardare la rete di amicizie come un grafo non orientato, in cui si cerca il percorso più breve tra 2 nodi. Questo algoritmo menzionato inizia la ricerca da entrambi i nodi allo stesso tempo, scopre i nodi vicini di quelli già noti. Quando le due superfici dei nodi noti si sovrappongono prima, viene trovato il percorso più breve.

Si prega di notare che alcuni casi speciali dovevano essere gestiti, come quando una delle persone si trova in una "isola" sul grafico, tale insieme di nodi che non è collegato ad altri nodi (si pensi ad una comunità senza rapporto con il mondo esterno)

La linea di fondo è un ciclo non troppo lungo.

Answer 2

È consigliabile eseguire una ricerca in ampie direzioni in entrambe le direzioni, ovvero da entrambi gli individui in questione, e interrompere questo processo quando si trova una connessione o si raggiunge il limite di profondità specificato. L'idea è anche di raggiungere prima gli individui più popolari (durante l'esecuzione di BFS)

Answer 3

RDBMS non è bravo a fare cose come questa.

Quello che ti serve è un graph db, e consiglio vivamente lo Neo4j, che è popolare e open source.

Answer 4

Quello che proverei prima è una ricerca in ampiezza.

Si noti che il codice seguente non funzionerà senza modifiche perché non ho nemmeno controllato gli errori di sintassi. La funzione query() dovrebbe restituire un elenco di voci come si vede. Ha lo scopo di darti un'idea.

/* 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); 
} 

Questo codice è stato ottimizzato per semplicità. Per tutto tranne i database di giocattoli, dovresti fare una ricerca bidirezionale in cui mantieni due liste, friended e friends (l'albero degli amici a f2). Dovresti estendere la lista più breve, cercando una corrispondenza nell'altra lista. Tuttavia non puoi ingannare la complessità, quindi dovrai mantenere il limite delle iterazioni a livelli molto bassi senza che ti piaccia il suono dei server di cestinazione.

Answer 5

Questo sarebbe con bordi aventi un peso di 1.C'è un sample code per calcolare la connessione tra 2 amici in un social network in PHP