Pathfinding - Kontakte über mehrere Ecken

[madden82]

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.

Sehr schon ist dieses Feature bei "openBC" zu sehen: http://www.openbc.com

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

[MelloPie]

kennt A den D denn wirklich? Also das würde ich in ner community als fraglich sehen wenn andere auf mein Profil geschickt werden, weil irgendjemand jemanden kennt der mich kennt...

Du könntest ne rekurisve Funktion bauen, die immer weiter geht solange jemand noch kontakte hat, allerdings kann das schnell deine kapazitäten fressen. Da solltest Du eine Kontakttiefe einschränken...

[TobiaZ]

*verschieb*

[mrhappiness]

Rekursiv ist ein gutes Stichwort.

Musst nur aufpassen, dass du jeden nur einmal erfasst, also bei der Konstellation
A -> B
B -> C
A -> C
C -> D
nicht C und alles, was dahinter kommt, doppelt aufführst

Da mySQL keine rekursiven Abfragen unterstützt (kann das eigentlich irgendeine freie Datenbank?), würde es sich anbieten, alle Kontakte von A auszulesen (deren IDs). Die IDs packst du in ein Array und liest alle Kontakte dieser IDs aus, außer den IDs selbst


Beim ersten Durchgang würdest du dann
B und C bekommen. beim zweiten Durchgang D (und C, aber das schließt du ja aus, daher bekommst du's doch nicht)
So solltest du dir auch keine Sorgen um Kapazitäten machen müssen und... Die Kontaktnähe ist auch richtig, denn D könnte in meinem Beispiel ein Kontakt auf 2. Ebene und ein Kontakt auf 3. Ebene sein, du bekommst ihn aber als Kontakt 2. Ebene geliefert.

Was der gute Dijkstra damit zu tun haben soll...

[penizillin]

ich denke, probleme mit kapazitäten müssten auch deswegen nicht auftreten, weil die "beziehungs-ebene" wohl eh' begrenzt sein wird - auf, sagen wir, 3 levels.

die bereits gefundenen partner, die man in dem array speichert (s. mrhappiness), kann man bereits bei der abfrage ausschließen, sodass man die zurückgelieferten ergebnisse direkt auswerten kann.

[madden82]

Die rekursive Lösung ist natürlich die "einfache" Lösung aber eben auch sehr rechenlastige Lösung. Da ich den "kürzesten Weg" finden möchte, muss ich ja wirklich alle Kontakte 2. und 3. Grades bei einer rekursiven Lösung abfragen...das wäre zu rechenlastig.

Kennt sich keiner mit "Dijkstra" oder "AStern" aus? Diesen sollen angeblich Algorithmen sein, mit denne ich mein Problem effizient lösen kann.



Viele Grüße
Martin

[kapitaeniglo]

hi

schon nen bissel her mit dem dijkstra,
aber das könnte eventuell etwas helfen ..

http://ciips.ee.uwa.edu.au/~morris/Y.../dijkstra.html

sonst einfach googeln

[mrhappiness]

Original geschrieben von madden82
Die rekursive Lösung ist natürlich die "einfache" Lösung aber eben auch sehr rechenlastige Lösung. Da ich den "kürzesten Weg" finden möchte, muss ich ja wirklich alle Kontakte 2. und 3. Grades bei einer rekursiven Lösung abfragen...das wäre zu rechenlastig.

Mit meiner Variante bekommst du doch den kürzesten Weg, ein eventuell vorhandener längerer Weg wird nicht verfolgt