Pathfinding - Kontakte über mehrere Ecken

Computer: Software & Programmierung PHP
#1

Hallo,

in unserer Community kann jedes Mitglied persönliche Kontakte besitzen.

Gerne würden wir ein Feature einbauen, mit dessen Hilfe sich jedes Mitglied darstellen lassen kann, über welche seiner persönlichen Kontakte er ihm bisher ihm unbekannte doch kennt.

Nicht so einfach der Satz, deswegen versuche ich es mal ein wenig konkreter an einem Beispiel zu erläutern:

Mitglied A kennt Mitglied B
Mitglied B kennt Mitglied C
Mitglied C kennt Mitglied D

So nun kennt A demnach auch D, nur nicht direkt sondern
A->B->C->D

D ist für A also ein Kontakt dritten Grades.

Wie kann ich sowas realisieren? Ich denke mal die Stichworte sind „Pathfinding“ und evtl. „Dijkstra“. Leider bin ich hier noch nicht so weit gekommen und hoffe hier im Forum Hilfe zu finden.

Eckdaten:

  • PHP
  • Tabelle mitglieder unteranderem mit Feld „mitglieds_id“
  • Tabelle kontakte mit dem Feld „mitglieds_id“, „kontakt_mitglieds_id“

Ich freue mich auf Antworten.

Viele Grüße aus Düsseldorf
Martin Berg

#2

Hi auch…

das was Dich vermutlich weiterbringen sollte ist eine Rekursive Funktion…

Das bedeutet eine Funktion, die sich selbst wieder aufruft…

Nun musst Du quasi so arbeiten…

function show_friends($mitglieds_id)
{
// diese Funktion sucht alle $kontakt_mitglieds_id 's, in der Akte von $mitglieds_id, und ruft dann show_friends($kontakt_mitglieds_id) auf.
(dein code)
show_friends($kontakt_mitglieds_id);
}

Bei Dir taucht aber jetzt ein delikates Problem auf…
Beispiel
A kennt B
B kennt C
C kennt D
D kennt A

nun kommen wir zum Schluss dass A sich selbst kennt - und zwar in vierter Ebene… und in achter, und in zwölfter und in sechzehnter…
Deswegen musst Du da unbedingt aufpassen, dass keine Zirkelbezüge auftauchen - die können aber auch auftauchen, wenn man nicht zurückgeführt wird auf A sondern auf B, der C kennt, der D kennt, der E kennt, der B kennt… Also fällt das ausschliessen der eigenen id da raus - ich würde da auf ein limit der ebenen zurückgreifen… Dir sollte aber bewusst sein, dass eine rekursive Funktion sehr viele mysql-Anfragen bedeutet und durch das Schneeballprinzip schnell sehr sehr viele Abfragen bewältigt werden müssen…
A kennt 20 leute, diese kennen wieder 20 - schon sind wir bei 420 Anfragen auf der zweiten Ebene… deswegen - sei vorsichtig mit sowas…

#3

Hi,

eine rekursive Lösung ist natürlich machbar, aber wie Du bereits geschrieben hast sehr rechenlastig.

Es muss da einfacherer Methoden geben. Stichwortw wie „Dijkstra“ und „AStern“. Ich bräuchte hier nur etwas Hilfe, denn verstehen tue ich die Algo’s bis jetzt nicht.

Vieleicht sind sie auf der falsche Ansatz?

Viele Grüße
Martin

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#4

hmmm… klingt für mich so als müsstest Du „nur“ ein array (vllt besser einen string) speichern, in dem alle id’s angegeben sind, die Du schon gecheckt hast…

und dann halt das query mit AND NOT anpassen…
So wird zumindest verhindert, dass Du zurückgehst…
Allerdings schützt das noch nicht davor, dass Du immer den kürzesten Weg gehst…
Das Problem in Deinem Fall ist, dass Du das Ziel nicht definiert hast… so kannst Du natürlich nicht gezielt nach dem kürzesten Weg zwischen beiden suchen sondern musst quasi den erstbesten nehmen und kannst maximal danach überprüfen, ob es nicht noch einen besseren (kürzeren) gibt…

Wenn Du Dir mal auf http://www.galactic-tales.de einen Charakter anlegst (keine Angst, kostet nix) dann gibst da einen NavComp… Der Berechnet die kürzeste Linie zwischen zwei Punkten (Ich arbeite da in der Anwenderbetreuung mit, deswegen weiss ich ein wenig wie das umgesetzt wurde).
Jedenfalls ist es da so, dass die kürzesten Wege dann in eine Datenbank geschrieben werden, falls diese Wege wieder abgefragt werden… Weil es eben sehr rechenintensiv ist so eine Berechnung anzustellen… Bei Dir können sich aber immer noch kürzere „Routen“ ergeben, deswegen geht das so leicht nicht bei Dir und deswegen warne ich eben schon mal vor… Wir haben 2 Server mit je 1 GB RAM und afaik je 2 1 GHz Prozessoren - wohlgemerkt - Only Webserver mit Loadbalancer… (DB liegt auf einem dritten Rechner)
Als die Datenbank aber noch leer war hatten wir ziemliche Performanceprobleme zu beklagen…