friendster, open BC, kontakte 6. Ebene

[ibekowies at shavingkiwis.de]

Hallo,

Vielen Dank fuer die Antwort!

Ja ich habe in einem Informatiker-Buch die Vorgehensweise für eine 
Breitensuche (Width First) in einem ungerichtetem Graphen. Das ganze 
ist nur nicht so gut in SQL und auf einen Graphen mit angesetzten 
500.000 Knoten (Personen) und einem Vielfachen an Kanten (Kontakte) 
umzusetzen. Ich habe in Mysql keine Rekursionen und es wäre auch 
Wahnsinn diese Datenmenge per Skript zu durchzusuchen (um besuchte 
Knoten zu markieren...).

deshalb such ich nach einer moeglichkeit das ganze mit hilfe von sql 
und speziell mit den eigenschaften von mysql zu implementieren 
(schnelle Reads, schnelle Temp-Tables, schlanke Tables, etc...)

Aber der Ansatz mit den Wolken ist interessant. ich muss denn ja nur 
noch die jeweilige Wolke durchsuche, in der beide vorhanden sind. Es 
kann nur sein, dass die "Wolken-Pflege" (hehe) zu aufwaendig wird. 
Auch ist es ja im schlimmsten nur eine riesenwolke.

Ich werde jetzt mal meinen urspruenglichen Ansatz testen, von beiden 
Seiten loszugehen (Die Testdatenbank aufzubauen hat den ganzen Abend 
gestern gedauert...)

Viele Gruesse, ILja


On 8 Feb 2005 at 7:36, Andreas Müller wrote:

> Hallo,
> das ist mal ein nettes Problem, aber auf MySQL etwas OT da an sich ein rein
> algorithmisches Problem. 
> 
> Zunächst sollte man feststellen das es beliebig viele "Ebenen" geben kann
> und das man auch eine Rückbezüglichkeit zu beachten hat (A kennt B, B kennt
> A).
> Je nach dem ob es auch den Fall gibt A kennt B aber B kennt A nicht gibt
> muss man das ganze uni- oder bi-direktional betrachten. Unidirektional wäre
> natürlich am einfachsten weil dann A kennt B und B kennt A nur eine
> Information ist. Hier sollte man sich auf eine Notation (z.B. x<y) einigen
> das man später gezielt suchen kann und nicht A,B und B,A testen muss.
> 
> Um nun den kürzesten Weg zu finden brauchst du eine rekursive Funktion die
> ausgehend von einem Punkt die ihm bekannten Punkte absucht. Von jedem
> gefundenen Punkt aus geht es nun rekursiv weiter, d.h. diese werden
> ebenfalls durchsucht. Dabei sollte man sich den bereits gegangenen Weg
> merken und aufpassen das man nicht im Kreis läuft. Das ganz geht solange
> weiter bis du einen Weg gefunden hast. Nun kennst du erstmal einen Weg. Auf
> deiner Suche hast du bereits einige Abstände zwischen Punkten merken können
> und evtl. durch frühere suchen in einer DB gespeichert:
> 
> E->G 2
> A->B 1
> etc.
> 
> Nun kannst du optimieren in dem du unter Zuhilfenahme der bekannten Abstände
> oder unter Erforschung neuer Abstände versuchst den einmal gefunden Weg zu
> verkürzen.
> 
> Es gäbe dazu noch eine alternative, die aber viel Speicherplatz benötigt:
> Man kann beim einfügen eines neuen Datensatzes die Abstände gleich
> berechnen. So entsteht eine Tabelle mit von,nach,Abstand und du kannst die
> Frage später sehr schnell beantworten. Je nach dem ob uni- oder
> bidirektional entstehen so n*(n-1)/2 oder n*(n-1) Datensätze.
> 
> Immer dann wenn es keinen Weg zwischen 2 Punkten gibt ist das Ansatzpunkt
> für weitere Optimierungen. Denn jetzt kann man hergehen und "Wolken"
> definieren, d.h. Listen von Punkten die überhaupt miteinander verbunden sein
> können. Auch sowas kann man bei der Erfassung der Daten bereits tun und
> somit wertvolle Suchzeit sparen. Aber immer dran denken: Ein neuer Kontakt
> kann Wolken verbinden.
> 
> Prinzipiell glaube ich das so ein Problem NP vollständig ist, kann mich aber
> auch gerade irren. Weiteres dazu in guten Algorithmenbüchern :-) 
> 
> Gruß,
> Andreas
> 
> 
> -- 
> Infos zur Mailingliste, zur Teilnahme und zum An- und Abmelden unter
> -->>  http://www.4t2.com/mysql 
> 
> 


-- 
Infos zur Mailingliste, zur Teilnahme und zum An- und Abmelden unter
-->>  http://www.4t2.com/mysql