[php][mysql] Połączenia pomiędzy użytkownikami

0

Witam,

mam problem ze strukturą bazy danych oraz sposobem rozwiązania dla następującego zagadnienia:

na stronie użytkonicy mają możliwości dodawania przyjaciół, więc do tego zrobiłem tabelez polami:

user_id,friend_id

będzie dużo użytkowników więc istnieje osobna tabela, dla uzytkowników zignorowanych i czekających na akceptację:

user_id,friend_id,type

wiadomo po zaakceptowaniu użytkownik zostaje przeniesiony do pierwszej tabeli

Teraz jeśli wchodzę na stronę jakiegoś użytkownika to chcę zobaczyć wspólnych przyjaciół oraz takich, których tylko on ma... więc mam takie zapytanie:

SELECT friend_id FROM tabela WHERE user_id = 1 AND friend_id  IN (SELECT friend_id FROM tabela WHERE user_id = 2) 

//czyli dotąd można powiedzieć, że mam gotowe i wiem jak zrobić

Do tego pojawia sie jeszcze jedno zagadnienie, gdy wejdę na stronę użytkownika, który nie jest moim znajomym, a jest znajomym mojego znajomego to musi się tam wyświetlić powiązanie, tj "ja -> mój znajomy -> użytkownik na którego stronie jestem" obsługiwane ma być maksymalnie 4 krotne zagłębianie, np "ja -> mój znajomy -> znjomy znajomego -> użytkownik" gdy do tego użytkownika nie ma powiązania w 4 krokach nic się nie wyświetla

Mógłby ktoś poradzić jak zaprojektować bazę dla tych powiązań i jak mniej więcej rowzwiązać to od strony php?
Myślę, że jeśli będe miał już bazę z php będzie mniejszy problem.

0

Ach, piszesz sieć społeczną?
Znajdowanie najkrótszej ścieżki w grafie po prostu - gdzie użytkownicy to wierzchołki, a połączenia pomiędzy nimi to krawędzie. Gdzie u ciebie najkrótsza ścieżka może mieć co najwyżej cztery wierzchołki po drodze.

Możesz użyć jakiegoś zmodyfikowanego algorytmu Dijkstry, ograniczającego ilość wierzchołków do czterech, a w tym grafie w dodatku wszystkie ścieżki mają taką samą wagę, ale nie wiem jak będzie z wydajnością, to jest tylko mój taki luźny pomysł na podstawie tego co wiem z teorii grafów.

Ostatnio Grono ujawniało w jaki sposób oni to realizują (http://itblog.grono.net/articles/2007/06/27/jak-dzia%C5%82a-wyszukiwanie-najkr%C3%B3tszych-%C5%9Bcie%C5%BCek).

Popatrz na: http://pl.wikipedia.org/wiki/Problem_najkr%C3%B3tszej_%C5%9Bcie%C5%BCki

1 użytkowników online, w tym zalogowanych: 0, gości: 1