kontaktscript

[ckeen]

kennt ihr openbc.com?

dort wird im account angezeigt, wie man mit einem anderen member verbunden ist.

(beispiel: man kennt person B & person B kennt person C & person C kennt person D, dann ist die verbindung A<>B<>C<>D, usw)

-> weiß jmd. wie man sowas in php/mysql realisieren kann?

[etreu]

Du hast in etwa eine Tabelle mit den Spalten A und B.

Du suchst alle Spalten A und/ oder B, wo die Person von der du ausgehst in der anderen Spalte stehst.

Mit allen gefundenen Personen gehst genauso vor. Dazu merkst du dir den "Pfad" den du genommen hast.

Was genau willst du machen? Vielleicht geht es ja auch einfacher.

[baba007]

kennt ihr openbc.com?

dort wird im account angezeigt, wie man mit einem anderen member verbunden ist.

(beispiel: man kennt person B & person B kennt person C & person C kennt person D, dann ist die verbindung A<>B<>C<>D, usw)

-> weiß jmd. wie man sowas in php/mysql realisieren kann?

binäre Bäume ? Nested Sets ? Worauf willst du hinaus ?

[ckeen]

nochmal zum besseren verstädnis:

folgendes Problem (so wie bei openBC):

Kontakte zwischen den usern: Man kann auf einen User klicken und sehen, über welche andere Personen man mit diesem User verbunden ist. Dies möchte ich auch realisieren und zwar auf mehreren Ebenen.

ginge natürlich mit der unelegante Lösung alle Verbindungen auszuprobieren, aber bei 10.000 leuten dürfte die performence dazu nicht mehr reichen.

Gibt es dafür einen eleganteren Lösungsweg?

-> hab an so ne art breitensuche gedacht, mein bisheriger ansatz:

verbindung zwischen ich und zielperson finden:

//maximalebene = wieviele ebenen tief soll gesucht werden

//anzf=anzahl der freunde in dieser ebene, für jede ebene neu auslesen

for (ebene=0; ebene<maximalebene; ebene++)

{

for (x=0; x<anzf; x++)

{

if ( freund[x] (ich) == zielperson) //verbindung gefunden

break;

}

}

-> wie lese ich jetzt die verbindungsfreunde aus/optimiere ich das ganze?

[etreu]

Allgemeiner Ansatz:

Du nimmst deine Ausgangsperson und packst sie in deine "Frontier". Hier ist all das drin, was du schon kennst. Die Frontier wird als FIFO behandelt. Dann gehst du solange die Queue durch, wie du Elemente hinzufügen kannst. Wenn du das nicht kannst, dann gehst du einen Schritt zurück und nimmst das zweite Element, usw.

Breitensuche liefert dir auf jeden Fall den kürzesten Weg.

[ckeen]

erstmal danke für die antwort, auch wenn ich bis auf breitensuche nur bahnhof verstehe.. (bin kein informatikstudent)

-> was bedeutet "Frontier" in diesem zusammenhang?

[etreu]

Frontier ist die Grenze, die alle Elemente deines Suchbaumes enthält, die bereits gefunden hast.

Ich hatte doch erwähnt, dass die Frontier als Queue gehandhabt wird. Und das ist eigentlich alles, was du für die Breitensuche brauchst.

Neue Personen die gefunden werden, werden hinten angehängt, sofern sie noch nicht drin sind.

[geloescht_JesterDay]

Wäre in diesem Fall eine Tiefensuche nicht besser geeignet, da er ja nicht nur wissen will, ob er irgendwie verbunden ist, sondern auch wie.

Also:

Du nimmst den Startknoten (die Person, die du ausgewählt hast) und folgst dem ersten Freund. Bist du dieser Freund lieferst du "ok" und den Knoten selbst zurück. Wenn nicht rufst du das rekursiv mit dem Freundknoten als Startknoten auf.

Wenn es keine weiteren Freundknoten gibt wird die Suche für diesen Knoten abgebrocen und "nicht ok" zurückgeliefert. Der aufrufende Knoten fährt dann mit dem nächsten Freund fort bzw. liefert auch "nicht ok" zurück wenn keine weiteren mehr vorhanden sind.

Wenn "ok" zurückkam wurde ja auch der Knoten mitgeliefert. An diesens Ergebnis hängt der aufrufende Knoten sich auch dran und gibt wiederum "ok" zurück. Am Ende hast du dann "ok" und eine Liste aller Knoten bis zu dir.

[ckeen]

glaube aber auch das breitensuche in diesem fall günstiger ist, wenn man nur eine verbindung haben will (mehr würde denke ich bei vielen membern zuviel performance wegnehmen).

und da es ja auch verbindungen über 1/2/3 ebenen geben kann, wäre es doch dumm, wie bei der tiefensuche jeweils gleich bis zur 4/5/... ebene zu suchen, oder?

[ckeen]

hab gerade nen neuen ansatz gefunden:

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

[geloescht_JesterDay]

und da es ja auch verbindungen über 1/2/3 ebenen geben kann, wäre es doch dumm, wie bei der tiefensuche jeweils gleich bis zur 4/5/... ebene zu suchen, oder?

Wenn die Verbindung nach 3 Ebenen da ist, suchst du ja nciht mehr weiter.

Bei der Breitensuche sehe ich nur eben keine Möglichkeit den genauen Weg zu bestimmen (also über wen bist du mit dieser Person verbunden). Es gibt nur die Möglichkeit destzustellen dass du eine Verbindung hast.

    B

  /    /

A- C - E - X

  \    \

    D

Nehmen wir mal an, du bist Person X und du hast auf Person A geklickt und willst wissen, über wen du mit dieser Person in Kontakt stehst.

Mit der Breitensuche prüfst du erstmal alle Freunde, also B, C und D, ob du eine davon bist. Wenn du das nicht bist, wird die Person in eine Liste aufgenommen mit zu prüfenden Personen. Vor der Aufnahme wird natürlich geprüft, ob die Person schon in der Liste ist. Dann fängst du am Anfang der Liste an ( und prüfst alle Freunde von B. Wenn der Freund nicht du bist, kommt er nach Prüfung hinten in die Liste. Sind alle Freunde von B geprüft geht es mit C weiter. Dann mit D, dann mit den Freunden von B, dann mit den Freunden von C und da, bei der Prüfung von E, wird dann festgestellt, du bist als Freund vorhanden. Und jetzt sag mir mal, wie du da den genauen Pfad feststellen willst um zu dir zu kommen?

(Die Buchstaben oben sind nur der einfachheithalber so gewählt. Die Reihenfolge B, C, D passt nur für eine Suche in der ersten Ebene. E kommt nicht mehr nach D.)

[ckeen]

stimmt, breitensuche fällt also weg..

wie löst man das sonst am besten?

[geloescht_JesterDay]

wie löst man das sonst am besten?

http://forum.fachinformatiker.de/890552-post8.html

Dein Floyd/Warshall fällt auch weg, weil du keine Gewichtung der Verbindungen hast bzw. ja alle gleich gewichtig sind.

[ckeen]

hm, obige lösung scheint aber ziemlich perfomenclastig zu sein, weil man ja im schlechtesten fall fast alle user durchgehen muss. -> wenn man 10.000+ user hat, macht das der server sicher nciht mehr mit, oder?

[geloescht_JesterDay]

hm, obige lösung scheint aber ziemlich perfomenclastig zu sein, weil man ja im schlechtesten fall fast alle user durchgehen muss.

Ja, im schlechtesten Fall musst du das, aber wie willst du denn unterscheiden (nochmal am obigen Beispiel), dass der Weg über C besser ist (weniger Kosten verursacht) als der Weg über B oder D? Das kannst du nicht, da du bei den Freunden keinerlei Gewichtung hast. Ein Freund ist genausogut wie der andere. Es gibt keine Möglichkeit das Abzukürzen.

Und auch eine Breitensuche wäre ja bei 10.000 Usern nicht unbedingt immer so viel kürzer. Nehmen wir mal an, Benutzer B hat keine Freunde, dafür hat Benutzer D 100, und die jeweils auch wieder einige. Dann wäre die Tiefensuche hier viel weniger aufwendig als die Breitensuche. Es kommt mir nämlich so vor, als wenn du dich generell von dieser Methode abwendest, weil sie nach deiner Ansicht auf jeden Fall immer langsamer und schlechter ist.

Da du keinerlei Vorhersage machen kannst, welcher Weg dich eher ans Ziel bringt, bleibt dir nichts anderes als alles zu probieren (wie beschrieben in meinem Algorythmus).

Du könntest, da alle Freunde gleichwertig sind, natürlich auch einen Zufallsgenerator einbauen, welchen Freund du zuerst prüfst. Bei ein paar Läufen hättest du dann vielleicht einen geringeren Aufwand als ohne Zufall, bei anderen aber auch wieder einen höheren.

Bu willst von A nach X einen Weg finden (s.o.). Hast aber keinerlei Anhaltspunkt welcher Weg besser geeignet ist. Wie stellst du dir denn eine Möglichkeit vor (auch nur ganz allgemein und abstrakt beschrieben), wie du hier einen Weg als besser auswählen kannst?

EDIT:

Außerdem musst du im Normalfall fast nie (fast) alle User durchgehen. Das wäre nur ein schlechter Fall. Wärst du der erste Freund von B, würdest du B prüfen, und dann den ersten Freund von B und die Prüfung wäre vorbei. Mit der Breitensuche würdest du B prüfen, dann C, dann D und dann würdest du erst gefunden werden. Also 2 Prüfungen zu 4 Prüfungen.

[ckeen]

ok, thx

[etreu]

Wieso habt ihr jetzt Breitensuche ausgeschlossen? Im Gegensatz zu Tiefensuche findet sie den kürzesten Weg. Und den Pfad zu merken, den man gegangen ist sollte ja wohl nicht das Problem sein.

Ausserdem kann es passieren, dass man bei der Tiefensuche in einen Zyklus läuft und da auch nicht mehr rauskommt, also nicht terminiert.

Breitensuche hingegen schon.

[geloescht_JesterDay]

Wieso habt ihr jetzt Breitensuche ausgeschlossen? Im Gegensatz zu Tiefensuche findet sie den kürzesten Weg. Und den Pfad zu merken, den man gegangen ist sollte ja wohl nicht das Problem sein.

Weil ich keinen akzeptablen Weg sehe, mit der Breitensuche den Weg zu merken. Bin aber mal auf einen Algo von dir gespannt, der das tut (und dabei nicht um etliches aufwendiger wird)

Ausserdem kann es passieren, dass man bei der Tiefensuche in einen Zyklus läuft und da auch nicht mehr rauskommt, also nicht terminiert.

Breitensuche hingegen schon.

In welchem genauen Fall denn? Hm... *überleg* Gut, wenn die Freundschaften zyklisch sind, also der 3.Knoten wieder den ersten als Freund hat. Aber da könnte man auch global eine Liste der besuchten Knoten mitführen (eine "Frontier") und vor dem rekursiven Aufruf dagegen prüfen...

Edit:

Außerdem kann es ja sein, dass er mit der geklickten Person nicht nur über eine Person verbunden ist, also sucht er nicht den kürzesten Weg, sondern alle Wege.

[geloescht_JesterDay]

hm, obige lösung scheint aber ziemlich perfomenclastig zu sein, weil man ja im schlechtesten fall fast alle user durchgehen muss. -> wenn man 10.000+ user hat, macht das der server sicher nciht mehr mit, oder?

Hab mir das gerade nochmal durch den Kopf gehen lassen...

also, angenommen mein Algorhytmus oben wird erweitert um die Prüfung, ob man den Knoten schon besucht hat, dann sieht es ja grob so aus:

- Prüfung ob der Knoten in der Liste

- Ja: Abruch. False zurück.

- Nein: Knoten == Ziel?

- Ja: Abbruch. True zurück. Eigenen Knoten an Ergebnisliste hängen.

- Nein: rekursiv mit nächstem Freundknoten aufrufen

- Zurück mit False.

Am aufwendigsten ist hier wohl die Prüfung ob der Knoten schon besucht wurde. Die Liste wird ja immer länger und muss einzeln durchlaufen werden. Daher meine Idee hierzu: Zu Beginn der Suche wird ein (eindeutiger) Zufallswert festgelegt (Hash aus aktuellen Mikrosekunden z.B.). Beim Prüfen eines Knotens wird dieser Wert als Kennzeichen des letzten Besuchers eingetragen. Die suche kennt ihren Wert und braucht nur zu prüfen ob der dasteht. Viel weniger aufwendig als eine Prüfung gegen eine Liste. Problem: keine 2 suchen gleichzeitig möglich, oder es muss für jede Suche ein eigener Baum aufgebaut werden. Wenn man sich auf eine Suche gleichzeitig beschränkt sollte das aber ok sein.

Also komme ich grob geschätzt auf ca 50 Takte die die CPU braucht um eine solche Prüfung zu durchlaufen. (Prüfung z.B. 2 Register füllen und Vergleichen hab ich auf 3 Takte ung. geschätzt und dann alles noch großzügig aufgerundet) Wobei die Schätzung wirklich sehr grob und ohne allzugenaue Kenntnis der tatsächlichen Vorgänge erfolgt ist. Aber ich schätze in Wahrheit ist es noch weniger, da der Prozessor aber auch ab und zu anderes tut denke ich 50 sind ok.

Laut Wikipedia:

Moderne Zentralprozessoren für PC führen heutzutage in einer Sekunde bis zu 4,8 Mrd. (4.800.000.000) Takte aus (Stand: 1/2005).

Wenn wir von diesen 4.8 Mrd. Takten pro Sekunde (und 50 Takten pro Knoten) ausgehen würdest du mit diesem Algo 96.000.000 (=96 Mio.) Knoten pro Sekunde prüfen können.

Über deine 10.000+ User lacht der Prozessor nur

P.S.: Wie gesagt alles nur sehr grobe Schätzungen, aber auf jeden Fall sind 10.000+ User absolut kein Problem. Selbst wenn ich mich um den Faktor 1000 verschätze dauert es dann nichtmal 1 Sekunde (genauer nichtmal 1/10 Sekunde).

[etreu]

So in etwa könnte das Ganze aussehen (nicht getestet). Datenbankzugriffe via ADODB (www.phplens.com/adodb).

$iterations = 0;

$known = array($myId);

$path = array(array($myId));

while ($iterations++ < MAX_DEPTH) {

    $list = implode("', '", $known);

    $sql = "SELECT person.A, person.B FROM person ".

                " WHERE ".

                    " person.A IN ('".$list."') AND person.B NOT IN ('".$list."') OR ".

                    " person.B IN ('".$list."') AND person.A NOT IN ('".$list."') ";

    $rs = $db->Execute($sql);

    if ($rs) {

        if ($rs->RecordCount() == 0) {

            // keine neuen Personen gefunden => Ende der Suche

            break;

        }

        else {

            $newpath = array();

            while (!$rs->EOF) {

                $row = $rs->FetchRow();

                if (in_array($row['A'], $known) {

                    $new = $row['B'];

                    $old = $row['A'];

                }

                else {

                    $new = $row['A'];

                    $old = $row['B'];

                }

                array_push($new, $known);

                //Pfade

                foreach($path in $item) {

                    if (end($item) == $old) {

                        array_push($new, $item);

                    }

                    array_push(array_merge($item, array($new)),$newpath);

                }

            }

            $path = $newpath;

        }

    }

    else {

        // Fehler in der Datenbankabfrage

    }

}

[/PHP]

[geloescht_JesterDay]

So in etwa könnte das Ganze aussehen (nicht getestet).

Mir wäre ein Pseudocode lieber gewesen, indem du einfach beschreibst was du tun willst.

IMHO tut dein Code gar nichts (bzw. ich kapiere nicht, was er tun soll). Das fängt schonmal beim sql an: Was ist person.A und person.B und wie stehen die in Beziehung? Person.A ist die Person und person.B jeweils ein eingetragener Freund? Dann würde es also auch person.A und person.C geben, wenn A 2 freunde hätte? Wobei C nur ein nur als weiterer Datensatz zu verstehen ist, der eben nur eine andere Person als Freund hat für person A.

Und wo wird bestimmt um welche Person es sich eigentlich handelt, von der du ausgehen willst? Also dein sql ist mir schonmal suspekt

Wie gesagt, erklär doch einfach mit Pseudocode was dein Algo tun soll. Ich sag ja nicht, dass meine Lösung die einzige und beste ist. Vielleicht stimmt dein Vorgehen ja und ich lern dabei dann was. Aber deinen Code kapiert man eben nicht so.

[etreu]

Für die eigenen ID habe ich einfach mal $myId genommen. Wo die herkommt ist mir eigentlich egal.

Ich gehe davon aus, dass person eine m:n Relation ist. Wobei ich aktuell davon ausgehe, dass diese Symmetrisch ist.

Vorgehen:

- Liste mit Personen die ich kenne ($known)

- Liste der Pfade ($path)

- SQL:

- es gibt das Paar A und B in der Tabelle

- ich suche alle Paare raus, in denen ich keine Person bereits kenne ( IN ... )

- ich weiss allerdings nicht, ob ich A oder B kenne ( ... OR ... )

- ich ignoriere die Ergebnisse, wo ich beide Personen kenne ( NOT IN )

- kein Ergebnis gefunden: keine neue Bekanntschaft

- Ergebnisse durchgehen:

- bestimmen, ob A oder B die neue Bekanntschaft ist ($new)

- festhalten, über wen die neue Person gefunden wurde ($old)

- die neue Person als bekannt merken (zu $known hinzufügen)

- Pfad bestimmen:

- alle Pfade suchen, an denen $old an letzter Stand

- neuen Pfad erstellen, in dem ich $new ranhänge

- jeder Pfad wird als Stack behandelt

- die neuen Pfade zu den alten hinzufügen (hier wird im Code aktuell eine Ersetzung vorgenommen)

- das ganze solange bis nichts mehr gefunden wird, oder bis die max. Suchtiefe erreicht wurde

Änderung im Code:

    array_push($new, $item);

    array_push($item,$newpath);

    // ...

    $path = array_merge($path, $newpath)

[/PHP]

[geloescht_JesterDay]

Also wir haben den Aufbau ung. so:

             I -O -P         B

           /         \        /

      C - D - J       Q - A - G

    /                           \

   B - E - K                    H

  / \    \        S   I

 /    F   U     /    / 

A - G - L - R - T -D - J

  \              \

    H - M         P

     \

      N

usw.

Gesucht ist, wie Person A mit Person P verbunden ist (z.B.). Du willst erstmal über eine SQL-Abfrage alle ... wirklich alle... möglichen Verbindungen Auslesen und in deiner Schleife durchgehen. In der Schleife sortierst du dann weiter aus, welche Person neu ist.

In deinem Pfad merkst du dir alle Personen, über die du eine neue Person gefunden hast. Bist du Person P erreicht hast, hast du aber alle Knoten gemerkt, bei denen du eine neue Person gefunden hast. Das ist im Beispiel oben so ziemlich das Alphabet zwischen A und P.

Tatsächlich ist der Weg aber: A-B-C-D-I-O-P

Außerdem gibt es auch noch den Weg: A-G-L-R-T-P

Ich sehe bei dir keine Lösung dazu. Oder ich kapier deinen Ansatz nicht...

Edit:

Außerdem gäbe es ja auch noch den Weg: A-G-L-R-T-D-I-O-P