Need Help, wer kennt wen über welchen ecken? wie realisiern?

mysteryxxx · 19.09.2008, 21:14

Hallo Leute

ich hab mal ne Frage wo wir bereits zu zweit verzweifelt sind da keiner eine Idee hat wie man das umzusetzen hat.

Und zwar wollen wir wie in studivz oder WKW diese Verbindung aufbauen. Also das teil wo man sieht über welchen ecken man sich kennt. Ich hoffe Ihr wisst was ich meine. Aber leider haben wir absolut keinen plan wo und wie wir damit anfangen.

Wir haben bereits schon mehrere Shopsystem und communitys programmiert aber bei diesem einen Teil sind wir grad buff und wissen nicht wie.

Kennt sich da jemand aus, kann man uns da tipps geben und etwas helfen?

nikosch · 19.09.2008, 21:16

Nicht trivial. Vermutlich Dijkstra.

mysteryxxx · 19.09.2008, 21:54

Danke für deine antwort *g* aber ich kann damit absolut nichts anfangen.

Ich bruach viel mehr input.

Wolla · 19.09.2008, 22:01

Das C-Programm brauchste doch nur noch nach PHP zu übertragen:
HowStuffWorks "How Routing Algorithms Work"

agrajag · 19.09.2008, 22:40

Wenn es dir nur darum geht die Verbindung zwischen 2 Usern zu berechnen und du das nur bis zu einer gewissen Tiefe ( z.B. maximal über 2 andere User) machen willst dann kannst du das mit SQL-JOINS lösen.

Ich hab sowas mal gemacht um Usern bei einem Profilbesuch anzuzeigen über wieviele Ecken sie den entsprechenden User kennen....

Das heißt eine Tabelle users (id, username, ...) und eine Tabelle users_users (a_user_id, b_user_id) über die die Freundschaften abgebildet werden. In users_users stehen pro Freundschaft 2 Einträge. Ist User 1 mit User 2 befreundet:

Code:

a_user_id | b_user_id
1 | 2
2 | 1

Dazu habe ich mir eine Funktion/Methode gebastelt, die mir die Verbindung von 2 Benutzern zurückgeben soll bzw. die mir immer den gesuchten User + alle zur Verbindung nötigen User zurückgibt.... Dazu werden einfach die beiden gewünschten User-Ids überben:

PHP-Code:

  function findConnection($id, $to_id){}

Für die direkte Verbindung reicht schon ein:

Code:

SELECT 
    A.*
FROM 
    users_users One
JOIN
    users A
ON
    A.id = One.b_user_id
WHERE
    One.a_user_id=$id
    AND
    One.b_user_id=$to_id

Das heißt in dem Fall wird eben aus der Verknüpfungstabelle users_users der Datensatz rausgesucht, bei dem a_user_id und b_user_id unseren gesuchten Usern entsprechen.
So weit so einfach

Spaßig wird es wenn das zu keinem Ergebnis geführt hat, dann kommt nochmal ein JOIN ins Spiel:

Code:

SELECT 
    A.*, B.*
FROM 
    users_users One 
JOIN 
    users_users Two 
ON 
    One.b_user_id = Two.b_user_id 
JOIN
    users A
ON
    A.id = One.b_user_id
JOIN
    users B
ON
    B.id = Two.a_user_id
WHERE 
    One.a_user_id = $id
    AND 
    Two.a_user_id=$to_id
LIMIT 1

Würde dir jetzt die Verbindung zweier User über einen weiteren User liefern. (bzw. die entsprechenden User-Datensätze)

Das ganze lässt sich jetzt noch bis zu beliebiger Tiefe weiterspinnen. Ab wann's gänzlich laaaangsam wird weiß ich nicht

Nicht schön, aber geht....

Flor1an · 20.09.2008, 12:13

Dijkstra ist hier nicht mal nötig. Der funktioniert in einem gewichteten Graphen, das haben wir hier aber nicht.

Für diese Suche ist einfach eine Breitensuche nötig. Aber da musst du auf bestimmte Dinge aufpassen.

1. User die du durch die Breitensuche schon besucht hast darfst du nicht wieder besuchen.

2. Wenn es KEINE Verbindung zwischen zwei Usern gibt dann kann es extrem lange dauern bis das Skript fertig ist.

3. Wäre es vielleicht sinnvoll eine Grenze ein zu bauen. Also z.B. nach 5 "Tiefen" einfach zu stoppen. Ich habe irgendwo mal gehört dass sich alle Menschen der Welt über 6 Ecken kennen. Also im Schnitt natürlich.

nikosch · 20.09.2008, 12:16

Obwohl ich solche Seiten nicht benutze, fände ich ein Netzwerk über 5 Ecken schon mehr als Blödsinn. Was habe ich mit Leuten zu tun, die ich über 4-5 andere kenne? Genau:

Flor1an · 20.09.2008, 15:18

Naja ansich ist es ja schon interessant zu wissen wen man über wen kennt. Grad wenn nur eine Person dazwischen ist findet man doch oft gemeinsame Freunde.

Und es kann dann natürlich durch aus vorkommen dass es halt mal 4-5 Personen zwischen einer anderen angeklickten Person sind. Auch wenn das dann eigentlich uninteressant ist.

Vielleicht sollte man dann die Breitensuche wirklich nur auf 3 Level begrenzen. Also wenn mehr als 2-3 Personen zwischen mir und der gesuchten Stehen dann macht es wirklich keinen Sinn mehr.

nikosch · 20.09.2008, 18:17

Das meinte ich ja.

mysteryxxx · 22.09.2008, 15:18

Da bin ich wieder mal

Danke @ Argrajag für deine Hilfe.

Also wir wollen das so machen wie bei studivz und wkw wo als startpunkt mein Bild kommt und end Punkt das Ziel bild und dazwischen 3 Verbindungen.

@Argrajag so wie ich verstanden hatte würde es also mit deinem Beispiel hier oben das gehen? Aber was super wichtig ist, ist das was Florian unter Punkt 1 und 2 gesagt hatte.
Ist das mit deinem Code so wie bei Studivz usw realisibar? (angenommen der user hat 2000 BEsucher) Hat ein Mensch nicht ich weis aber es gibt immer so spinner

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Newsletter - need help	TeazY	PHP Tipps 2008	4	03.01.2008 19:25
Layout schwimmt - need help !	php1	HTML, Usability und Barrierefreiheit	6	14.12.2005 17:57
Geburtstaggsgeschenk für meinen Dad...need Help please		PHP Tipps 2005	14	09.04.2005 17:20
frage nach bestimmten funktionen -> Update need more help		PHP Tipps 2005	13	23.03.2005 10:09
I need help - PHP&MySQL		PHP Tipps 2005	5	09.02.2005 15:13
need help: <prev \| next> bei viewpic...	denax	PHP Tipps 2005	7	15.01.2005 17:32
Button soll mehrere Ereignisse starten !? need your help		PHP Tipps 2004	5	27.07.2004 18:00
need Help zu PHPSESSID vs valid XHTML		PHP Tipps 2004	2	22.07.2004 16:47

19.09.2008, 21:14
mysteryxxx Benutzer Registriert seit: 04.06.2008 Beiträge: 30	Need Help, wer kennt wen über welchen ecken? wie realisiern? Hallo Leute ich hab mal ne Frage wo wir bereits zu zweit verzweifelt sind da keiner eine Idee hat wie man das umzusetzen hat. Und zwar wollen wir wie in studivz oder WKW diese Verbindung aufbauen. Also das teil wo man sieht über welchen ecken man sich kennt. Ich hoffe Ihr wisst was ich meine. Aber leider haben wir absolut keinen plan wo und wie wir damit anfangen. Wir haben bereits schon mehrere Shopsystem und communitys programmiert aber bei diesem einen Teil sind wir grad buff und wissen nicht wie. Kennt sich da jemand aus, kann man uns da tipps geben und etwas helfen?


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

19.09.2008, 21:16
nikosch moderatives Dielektrikum Registriert seit: 21.05.2008 Beiträge: 35.988 PHP-Kenntnisse: Fortgeschritten	Nicht trivial. Vermutlich Dijkstra. __________________ -- One pixel is still too big. Please make it smaller. ASAP. Initiative Mittelstand. Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers. --

19.09.2008, 21:54
mysteryxxx Benutzer Registriert seit: 04.06.2008 Beiträge: 30	Danke für deine antwort g aber ich kann damit absolut nichts anfangen. Ich bruach viel mehr input.

19.09.2008, 22:01
Wolla Moderator Registriert seit: 06.06.2008 Beiträge: 4.945 PHP-Kenntnisse: Fortgeschritten	Das C-Programm brauchste doch nur noch nach PHP zu übertragen: HowStuffWorks "How Routing Algorithms Work"

19.09.2008, 22:40
agrajag Moderator Registriert seit: 02.10.2006 Beiträge: 3.820 PHP-Kenntnisse: Fortgeschritten	Wenn es dir nur darum geht die Verbindung zwischen 2 Usern zu berechnen und du das nur bis zu einer gewissen Tiefe ( z.B. maximal über 2 andere User) machen willst dann kannst du das mit SQL-JOINS lösen. Ich hab sowas mal gemacht um Usern bei einem Profilbesuch anzuzeigen über wieviele Ecken sie den entsprechenden User kennen.... Das heißt eine Tabelle users (id, username, ...) und eine Tabelle users_users (a_user_id, b_user_id) über die die Freundschaften abgebildet werden. In users_users stehen pro Freundschaft 2 Einträge. Ist User 1 mit User 2 befreundet: Code: a_user_id \| b_user_id 1 \| 2 2 \| 1 Dazu habe ich mir eine Funktion/Methode gebastelt, die mir die Verbindung von 2 Benutzern zurückgeben soll bzw. die mir immer den gesuchten User + alle zur Verbindung nötigen User zurückgibt.... Dazu werden einfach die beiden gewünschten User-Ids überben: PHP-Code: `function findConnection($id, $to_id){}` Für die direkte Verbindung reicht schon ein: Code: SELECT A.* FROM users_users One JOIN users A ON A.id = One.b_user_id WHERE One.a_user_id=$id AND One.b_user_id=$to_id Das heißt in dem Fall wird eben aus der Verknüpfungstabelle users_users der Datensatz rausgesucht, bei dem a_user_id und b_user_id unseren gesuchten Usern entsprechen. So weit so einfach Spaßig wird es wenn das zu keinem Ergebnis geführt hat, dann kommt nochmal ein JOIN ins Spiel: Code: SELECT A., B. FROM users_users One JOIN users_users Two ON One.b_user_id = Two.b_user_id JOIN users A ON A.id = One.b_user_id JOIN users B ON B.id = Two.a_user_id WHERE One.a_user_id = $id AND Two.a_user_id=$to_id LIMIT 1 Würde dir jetzt die Verbindung zweier User über einen weiteren User liefern. (bzw. die entsprechenden User-Datensätze) Das ganze lässt sich jetzt noch bis zu beliebiger Tiefe weiterspinnen. Ab wann's gänzlich laaaangsam wird weiß ich nicht Nicht schön, aber geht.... __________________ Today you...Tomorrow me.

20.09.2008, 12:13
Flor1an da schreibt der ElePHPant Registriert seit: 18.06.2008 Beiträge: 8.903 PHP-Kenntnisse: Fortgeschritten	Dijkstra ist hier nicht mal nötig. Der funktioniert in einem gewichteten Graphen, das haben wir hier aber nicht. Für diese Suche ist einfach eine Breitensuche nötig. Aber da musst du auf bestimmte Dinge aufpassen. 1. User die du durch die Breitensuche schon besucht hast darfst du nicht wieder besuchen. 2. Wenn es KEINE Verbindung zwischen zwei Usern gibt dann kann es extrem lange dauern bis das Skript fertig ist. 3. Wäre es vielleicht sinnvoll eine Grenze ein zu bauen. Also z.B. nach 5 "Tiefen" einfach zu stoppen. Ich habe irgendwo mal gehört dass sich alle Menschen der Welt über 6 Ecken kennen. Also im Schnitt natürlich.

20.09.2008, 12:16
nikosch moderatives Dielektrikum Registriert seit: 21.05.2008 Beiträge: 35.988 PHP-Kenntnisse: Fortgeschritten	Obwohl ich solche Seiten nicht benutze, fände ich ein Netzwerk über 5 Ecken schon mehr als Blödsinn. Was habe ich mit Leuten zu tun, die ich über 4-5 andere kenne? Genau: __________________ -- One pixel is still too big. Please make it smaller. ASAP. Initiative Mittelstand. Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers. --

20.09.2008, 15:18
Flor1an da schreibt der ElePHPant Registriert seit: 18.06.2008 Beiträge: 8.903 PHP-Kenntnisse: Fortgeschritten	Naja ansich ist es ja schon interessant zu wissen wen man über wen kennt. Grad wenn nur eine Person dazwischen ist findet man doch oft gemeinsame Freunde. Und es kann dann natürlich durch aus vorkommen dass es halt mal 4-5 Personen zwischen einer anderen angeklickten Person sind. Auch wenn das dann eigentlich uninteressant ist. Vielleicht sollte man dann die Breitensuche wirklich nur auf 3 Level begrenzen. Also wenn mehr als 2-3 Personen zwischen mir und der gesuchten Stehen dann macht es wirklich keinen Sinn mehr.

20.09.2008, 18:17
nikosch moderatives Dielektrikum Registriert seit: 21.05.2008 Beiträge: 35.988 PHP-Kenntnisse: Fortgeschritten	Das meinte ich ja. __________________ -- One pixel is still too big. Please make it smaller. ASAP. Initiative Mittelstand. Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers. --

22.09.2008, 15:18
mysteryxxx Benutzer Registriert seit: 04.06.2008 Beiträge: 30	Da bin ich wieder mal Danke @ Argrajag für deine Hilfe. Also wir wollen das so machen wie bei studivz und wkw wo als startpunkt mein Bild kommt und end Punkt das Ziel bild und dazwischen 3 Verbindungen. @Argrajag so wie ich verstanden hatte würde es also mit deinem Beispiel hier oben das gehen? Aber was super wichtig ist, ist das was Florian unter Punkt 1 und 2 gesagt hatte. Ist das mit deinem Code so wie bei Studivz usw realisibar? (angenommen der user hat 2000 BEsucher) Hat ein Mensch nicht ich weis aber es gibt immer so spinner Geändert von mysteryxxx (22.09.2008 um 15:42 Uhr).