Wie funktionieren openBC-Verbinden?

**tommie82** · 14.08.2006, 20:24

Hi,

also wie es tatsächlich umgesetzt ist kann ich dir nicht sagen, allerdings bist du auf jeden Fall im falschen Forum, weil dies zu DB-Strukturen, also SQL / Datenbanken gehört. Eine programmiertechnische Lösung würde ich sofort verwerfen.

Ich weiß nicht ob ich damit richtig liege, aber so wie Indexe als B/B+ Bäume abgelegt sind könnte man sicherlich auch diese Art von Beziehungen in einer Baum-Struktur ablegen und dann bequem und performant durchlaufen. Ist allerdings nur eine Vermutung, da wirst du wohl jemanden fragen müssen, der wesentlich mehr Ahnung von DBMS hat oder in einem schlauen Buch nachlesen, wenn du selber sowas umsetzen willst.

Grüße
tommie

**foxroberts** · 14.08.2006, 23:08

Wie funktionieren openBC-/Friendster-Verbindungen?

Hallo.

Das Prinzip ist immer das gleiche:
Man wählt eine Person aus, und das System zeigt
den Weg über andere Personen auf.

Ich -> Klaus -> Manfred -> Uschi -> Zielperson

Ich frage mich wie dies programmiertechnisch zu
lösen ist, da mir höchstens sehr aufwendige Wege
einfallen wollen und ich denke, dass das System
"on the fly" alle Verbindungen aller Bekannten
durchläuft bis "zufällig" eine passende gefunden wurde.

Wenn jemand eine Idee hat oder weiß, wie diese
Netzwerk-Anzeigen funktionieren, bitte posten!

Vielen Dank!
Fox

**prego** · 14.08.2006, 23:55

Hi,

ich finds grad nicht, aber ich hab dazu schon mal einige Links gepostet.

Das ganze ist sehr aufwändig. Es geht hier um Graphentheorie. Wir haben hier sowas laufen und implementiert. Es geht darum den "kürzesten" Weg durch ein Netzwerk von Knoten (Usern) zu finden. Es gibt meines Wissens keine Möglichkeit das on-the-fly zu machen. Man muss sich jeden Knoten im Graphen anschauen und gucken ob man über diesen einen Weg zum Zielknoten findet.

Es gibt mehrer Möglichkeiten diesen Weg herraus zu finden. Entweder man sucht alle Verbindungen von A nach B mit der minimalsten Dinstanz, oder man sucht nur eine Verbindung.
Wenn mann alle Verbindungen suchen will, kann das - je nach größe des Graphen - schon ein wenig dauern. Bei einer Verbindung lässt sich das relativ schnell mit dem Dijkstra Algorythmus bewerkstelligen. Vorraussetzung für beides ist allerdings das man das komplette "Netzwerk" (also den Graphen) vorhält, so das der Algorithmus darauf arbeiten kann.

Folgende Links kann ich dir empfehlen:
http://de.wikipedia.org/wiki/A*-Algorithmus
http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra
http://de.wikipedia.org/wiki/Algorit...d_und_Warshall

//Edit:
Eine sehr schöne Erklärung ist hier zu finden:
http://mandalex.manderby.com/d/dijkstra.php?id=93

**foxroberts** · 15.08.2006, 00:52

Vielen Dank!

Der ist mir der liebste:
http://computer.howstuffworks.com/ro...algorithm3.htm

Falls jemand eine PHP-Version davon besitzt,
wäre ein Posting sicherlich für viele nützlich.

Fox

**foxroberts** · 15.08.2006, 00:59

Just in case:
http://en.giswiki.org/wiki/Algorithmus_von_Dijkstra#PHP

**123456** · 31.08.2006, 02:42

Wie verwende ich den Algorithmus denn? Leider bin ich kein Mathematik-Ass... Ich habe fleißig gegooglet aber finde einfach keine Hilfe wie ich den Algorithmus anwenden kann, um eine Verbindung zwischen verschiedenen Usern zu ermitteln. Vielleicht kann mir jemand helfen?

Mal angenommen ich hätte eine DB in der nach folgendem Schema die Verbindungen eingetragen sind:

userid1|userid2
----------------
2342|765
12|2387
765|234
...

Bei dem genannten Script
http://en.giswiki.org/wiki/Algorithmus_von_Dijkstra#PHP

Wie bzw wo müssen die Werte denn im Array '$points ' auftauchen?
Wie sähe hier beispielsweise das Array aus?

Und welche Werte müsste ich der Matrix-Breite sowie der Distanz übergeben, so dass ich bei einer Abfrage der kürzesten Verbindung zwischen 2342 und 234 als Resultat das Ergebnis herausbekomme:

2342=>765=>234

Ich bin dankbar für jede Hilfe!

Sebastian

**intermedia** · 01.09.2006, 14:14

Hi,

das Thema ist sehr komplex, aber als Stichwort nenne ich mal "Rekursion" und "Nested Set".

Damit läßt sich sowas realisieren.

Hier mal ein Link: http://www.php-resource.de/tutorials/read/21/1/

Gruß Sven

**onemorenerd** · 01.09.2006, 14:25

Ich habe den Thread zwar nicht komplett gelesen, aber die letzte Frage war doch, wie man bei der Implementierung von Dijkstra richtig initialisiert.

@123456: Hast du das Beispiel mal versucht? Was hast du nicht verstanden, warum kannst du das nicht auf deine Daten ummünzen?
Oder scheitert es wirklich daran, die Daten aus der DB zu holen?

**123456** · 04.09.2006, 12:28

@intermedia: Das Problem der Rekursion ist ja der Performance-Verlust. Der Dijkstra-Algorithmus scheint dort angeblich effektiver zu sein wenn es sich um eine großere Anzahl von Verbindungen handelt.

@Sven: Ja genau das Beispiel habe ich ausprobiert. Jedoch kann ich die Funktion nicht passend ummünzen,da ich nicht weiß welche Werte ich '$matrixWidth' und '$points' übergeben muss. Es scheitert also nicht daran, dass ich nicht weiß wie ich die Werte aus der Mysql-DB auslesen kann.

Hier z.b.:

// $points is an array in the following format: (router1,router2,distance-between-them)
$points = array(
array(0,1,4),
array(0,2,I),
array(1,2,5),
array(1,3,5),
array(2,3,5),
array(3,4,5),
array(4,5,5),
array(4,5,5),
array(2,10,30),
array(2,11,40),
array(5,19,20),
array(10,11,20),
array(12,13,20),
);

In meinem Fall müsste das doch so aussehen:

$points = array(
array(id_Freund_x,id_Freund_y,Abstand),
...
);

Wobei der Abstand immer gleich "1" sein dürfte, da ja in meiner DB nur eine Tabelle mit den unmittelbaren Freundschaftsrelationen existiert.
Wie kann ich denn mit dem Algorithmus den Weg oder die Knotenpunkte der kürzesten Verbindung von z.b. "id_Freund_z" zu "id_Freund_x" ermitteln?
z.b. "id_Freund_z"=>"id_Freund_g"=>"id_Freund_y"=>"id_Freund_x"

Vielen Dank
Sebi

**Friedward74** · 14.06.2007, 13:23

Lösung gefunden?

Hi 123456 ,

hast Du inzwischen eine Lösung gefunden. Ich bin nämlich dabei eine nahezu identische Anwendung zu basteln?

Wär dankbar für nen Tip,

Gruß,
F.

**penizillin** · 14.06.2007, 18:19

Friedward74, ich würde mir keine hoffnungen machen, dass 123456 wiederkommt, schau mal, wann er das letzte mal geschrieben hat. beschreibe lieber dein problem.

**Friedward74** · 14.06.2007, 23:08

Initialisierung des Arrays

Hi penizillin,

hab ich gesehen und ihm daher auch noch ne Email geschrieben, aber bisher noch keine Antwort. Also ich hab auch eine DB mit Freundschaftsbeziehungen

ID Freund1 Freund2
1     1     2
2     2     3
3     4     5
4     3     6
.
.
.
Wie initialisiere ich jetzt das Array aus der SQL-Abfrage heraus?

Wird dann die gesamte DB mit mehreren Tausend Beziehungen in das Array geschrieben? Da leidet die Performance doch extrem, oder?

Danke für die Hilfe,
F.

**penizillin** · 14.06.2007, 23:25

warum sieht die tabelle so aus? ist denn 1 mit 2 befreundet, aber nicht andersherum? weißt du, wie man graphen speichern kann?

hier, ein wenig theorie, die die notwendigen suchbegriffe liefert:

http://www.casos.cs.cmu.edu/publicat...SRI-04-135.pdf
http://www.artfulsoftware.com/mysqlb...qled1ch20.html
http://www.tutorials.de/forum/relati...auflisten.html

**Friedward74** · 15.06.2007, 09:08

Freundschaftsbeziehungen

Hab die Artikel gelesen, bin aber noch nicht viel schlauer. In einem wird wie Du angedeutet hast, die Beziehung der beiden Freunde doppelt aufgeführt ( 1 ist mit 2 befreundet und 2 ist mit 1 befreundet). Allerdings erschließt sich mir nicht ganz der Sinn.
In den anderen geht es wohl mehr um Baumdiagramme (z.B. für Stammbäume).

Natürlich sind auch bei mir beide User (1+2) gegenseitig miteinander befreundet. In meiner DB sieht´s nur so aus, dass jede Freundschaftsbeziehung nur einmal abgelegt wird. Freund1 ist der einladende und Freund2 der, die Freundschaft annehmende Freund. Würde obige Struktur die DB nicht eh nur unnötig aufblähen?

Auch bei den oben erwähnten Beispielen und der aufgeführten Array-Initialisierung ist hiervon nicht die Rede. Nur wie initialisiere ich das Array über ne MySQL-Abfrage am intelligentesten. Ich will ungern bei jeder Beziehungsabfrage die gesamte Tabelle ins Array shiften, oder ist das der richtige Weg?

Gruß,

F.

Wie funktionieren openBC-Verbinden?