NeoVanGoth: "Pfad" durch Verknüpfungen finden

SELF-Forum

"Pfad" durch Verknüpfungen finden

NeoVanGoth
– Informationen zu den Bewertungsregeln

Hi!

Vielleicht kann mir einer von euch weiterhelfen:
Ich habe eine n-zu-n Verknüpfungstabelle, welche die Freundeslisten einer Community darstellt, d.h. jeweils eine User-ID ist mit irgendeiner anderen verknüpft.
Was ich gerne herausfinden würde, wäre eine Möglichkeit, einen möglichst kurzen "Pfad" von einer beliebigen User-ID zu einer beliebigen anderen zu finden und somit darzustellen, über wie viele und welche "Ecken" jemand jemanden anderen kennt (gibts z.B: bei Lokalisten und StudiVZ).

Die einzige Möglichkeit die mir einfällt ist, rekursiv alle möglichen Verknüpfungen durchzugehen, bis die finale User-ID gefunden wird. Obwohl man alle schon gefundenen IDs in tieferen Levels ausnehmen könnte, würde das afaik trotzdem sehr schlecht skalieren.

Kennt irgendjemand eine sinnvolle Möglichkeit?
Technisch habe ich PostgreSQL mit Functions per Plpgsql zur Verfügung.

Danke an alle!

Beitrag melden
–
Informationen zu den Bewertungsregeln

  1. "Pfad" durch Verknüpfungen finden

    NeoVanGoth
    – Informationen zu den Bewertungsregeln

    Hi,

    zwei Tassen Kaffee später bin ich etwas weiter...
    Es handelt sich um einen unzusammenhängen, ungerichteten und ungewichteten Graphen, ein skalenfreies Netz. Relativ eklig, da man weder die Länge des Pfades abschätzen kann, noch davon ausgehen kann, dass wirklich ein Pfad existiert.

    Als Ansatz habe ich jetzt, dass ich den Pfad von beiden Seiten aus iteriere, d.h. jeweils alle Verknüpfungen des aktuellen, aufsteigenden Levels suche und jeweils mit allen schon gefundenen Links auf der anderen Seite - beginnend mit dem niedrigsten Level - vergleiche.

    Mal nen Test-Algo bauen...

    Beitrag melden
    –
    Informationen zu den Bewertungsregeln

    1. "Pfad" durch Verknüpfungen finden

      Frank (no reg)
      – Informationen zu den Bewertungsregeln

      Servus,

      http://de.wikipedia.org/wiki/Graphentheorie
      http://de.wikipedia.org/wiki/Algorithmus_von_Floyd_und_Warshall

      Da stehen bereits einige Theorien zur "Graphentheorie" :)

      Ciao, Frnak

      Beitrag melden
      –
      Informationen zu den Bewertungsregeln

      1. "Pfad" durch Verknüpfungen finden

        NeoVanGoth
        – Informationen zu den Bewertungsregeln

        Servus,

        http://de.wikipedia.org/wiki/Graphentheorie
        http://de.wikipedia.org/wiki/Algorithmus_von_Floyd_und_Warshall

        Da stehen bereits einige Theorien zur "Graphentheorie" :)

        Ciao, Frnak

        Uff, irgendwie ist mir das etwas zu hoch... aber ich glaube, ich habs hinbekommen, zumindest in einem PHP-Test, die Suche verläuft jetzt zuverlässig und effektiv.

        Ich versuche gerade, das ganze mit Plpgsql innerhalb meiner PostgreSQL als Funktion umzusetzen, da wirds richtig eklig...

        Danke jedenfalls!

        Beitrag melden
        –
        Informationen zu den Bewertungsregeln