Hallo allerseits!

Folgendes Problem (so wie bei openBC zu sehen):

User können sich miteinander "verbinden". 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.

Momentan fällt mir da nur eine unelegante Lösung ala alle Verbindungen ausprobieren ein. Gibt es dafür evtl. einen eleganteren Lösungsweg?

Gruß Moritz.

Hört sich nach einem klassischen „traveling salesman“ Problem an, danach in Kombination mit "Graph" zu suchen sollte dir einige gute Methoden liefern.

Hallo,

das Thema hatten wir bereits mal angeschnitten, vielleicht hilft es ja etwas auf die Sprünge, ob ein Algorithmus nun besonders gut ist, kann ich so nun nicht sagen, da ich es selber wohl noch nie realisiert habe. Es war aber mal ein kurzes Gedankenspiel von mir, wie man es vielleicht machen könnte.

http://www.ayom.com/topic-10876.html



MfG Sascha Ahlers

Habe mir gestern Nacht zu diesem Thema noch ein paar Gedanken gemacht. Wenn ich davon ausgehe, dass das Projekt 10.000 User hat, die sich untereinander verlinken, denke ich nicht, dass es gut wäre jedes mal die Verbindung mit einen Algorithmus zu überprüfen. Das würde einfach zu lange dauern.

Andere Möglichkeit wäre, dass ich drei Tabellen anlege:

Ebene1: User1, User2
Ebene2: User1, Link1, User2
Ebene3: User1, Link1, Link2, User3

Gehen wir davon aus, dass es keine Überschneidungen der Freundeskreise gibt (unrealistisch, aber nur zum Rechnen) und jeder User hat 20 Freunde, die wiederum 20 Freunde haben.

Bei drei Ebenen gibt es pro User 20*20*20 = 8000 Datensätze * 10.000 User = 80.000.000 Datensätze.

Nun, ich habe schon Projekte in MySQL durchgeführt, die bis zu drei Millionen Datensätze in einer Tabelle haben. Aber wie sieht es aus, wenn man von >100 Millionen ausgeht? Ist dann noch eine ausreichende Performance gegeben? Was haltet ihr von diesen Ansatz?

Ich hab mal eine TV Doku gesehen, in der eklärt wird, wie der Navi Algo funktionerit. Im Prinzip suchst du einen solchen Algorythmus.

Das hört sich irgendwie nach einer Menge überflüssiger Daten an, wobei die Proformence durch die Größe der Tabelle bei schlechter Struktierung (, wenn eine solche Tabelle überhaupt gut strukturiert werden kann,) auch leidet.



MfG Sascha Ahlers

Meinst du mit Navi Algorithmus den für Navigationsinstrumente? Das wäre dann ja der Travelling Salesman, wenn ich mich nicht irre.

Aber mein Gedanke ist, dass es besser ist, die Verbindungen in einer "Ebene2" und "Ebene3" Tabelle abszuspeichern, als nur eine "Ebene1" Tabelle zu haben und diese dann immer mit einen Algorithmus auszugeben. Das Problem bei drei Ebenen Tabellen wäre halt die ungeheure Menge von Datensätzen....

@Sascha: Ja, das ist es natürlich. Aber evtl. trotzdem schneller als die Bearbeitung mit dem Travelling Salesman Algo?

Kann es sein, dass das Travelling Salesman Algorithmus im Deutschen dem Ameisenalgorithmus [1] entspricht?
Nach meinen ersten gefunden Informationen hat es auf jedenfall den Anschein. Ich würde aber mal behaupten, dass ich es nicht direkt nach diesen Algorithmus bzw. zumindestens in ziemlich abgeänderter Weise lösen würde, aber die Speicherung unmengen von Datensätzen würde mir auch ziemlich widerstreben.



MfG Sascha Ahlers

[1] Wikipedia: Ameisenalgorithmus

Ja, der Ameisenalgorithus ist ein Lösungsweg. Ich hatte mich falsch ausgedrückt: Es gibt das Travelling Salesman Problem (nicht Algorithmus), für das es halt mehrere Lösungswege gibt.

Ich bin mir jetzt wirklich unsicher, wie ich vorgehen soll... Ich werde mir die Algorithmen noch einmal genauer angucken....

Das Problem selbst ist ja eigentlich nicht ein genaues Travelling Salesman Problem, da er ja nicht alle Punkte abgehen will, sondern „nur“ die kürzeste Verbindung zweier Punkte gesucht wird. (Dijkstra Algorithmus http://www.graph-magics.com/articles/shortest_path.php).

Mein Hinweis war eigentlich ungenau weil ich das Problem nicht genau genug angesehen hatte.
Trotzdem ist es schon ein Klassiker in der Graphentheorie, das Problem ist wohl nicht mal so sehr das effizient abzuarbeiten. Das aber Datenbankfreundlich zu machen ist sicher nicht ganz so einfach.

genau, den meinte ich mit Navi....

Mein FF hat meine Antwort verschluckt, also nochmal eher kurz:
Dein Graph ist unzusammenhängen, ungerichtet und ungewichtet. Es handelt sich in der Tat nicht um TS, sondern um ein shortest path problem. Dijkstra (Ford-Bellmann etc.) bringen nichts, weil sie für gewichtete Kanten sind. Spannbäume kannst Du auch nicht machen, da der Graph nicht vollständig ist. Imho kannst Du iterieren und cachen, oder Du beschränkst Dich darauf die Distanz zw. Dir und dem andern Mitlgied anzuzeigen. Da kannst Du mittel dynamischer Rekursion einigermassen Performant einen zweiten Graph bauen (den Distanzgraph) indem Du die Distanz zwischen 2 Leuten solange berechnest, indem Du bei jedem Schritt prüfst ob es diese Distanz schon gibt.

Ich bin an diesem Punkt der Meinung, dass es quasi unmöglich ist einen wirklich effektiven Algo zu bauen, solange der Graph unvollständig ist. Die Zerlegung in vollständige Graphen ist auch sinnlos. Mach Dir vor allem Überlegungen zum Datentyp. Manchmal ist es sehr viel schneller, wenn Du eine Adjazenten-Matrix generierst und damit rechnest, anstelle für jede Ebene eine Query an die DB zu sendne.

Leider weiß ich nicht, was eine Adjazenten-Matrix ist...

Eigentlich kann man bei einem ungewichteten Graphen immer vom Gewicht 1 ausgehen ;-)
Ich habe mal für einen Verkehrsverbund an einer Fahrplanabfrage gearbeitet. Da hat man sich letztlich dafür entschieden, dass man alle Varianten berechnet und abspeichert da es in diesem Fall nicht so oft zu Änderungen kam die eine neue Berechnung notwendig machten.

Die Theorie läst sich mit den gefallenen Stichworten jetzt wohl wirklich leicht finden.

Eine A-Matrix in Deinem Fall musst Du Dir so vorstellen: Für jedes Mitglied i, dass mit dem Mitglied j verbunden ist, steht in der i-ten Zeile und der j-ten Spalte eine 1. Sonst 0. Für weitere Erklärungen, bitte googlen. Da Du sehr viele Nullen und sehr wenig 1en hast, ist Dein Graph nicht vollständig (d.h. nicht jedes Mitgl. kann von jedem Mitgl. aus erreicht werden). Deshalb wäre [sparse Matrix] für eine Implementation in Betracht zu ziehen. Wenn ich richtig davon ausgehe, dass Dein Graph ungerichtet ist (wenn ich mich mit Dir verbinde, bist auch automatisch Du mit mir verbunden), dann kannst Du Dich auf eine obere (untere) Dreiecksmatrix beschränken.

;-)
Genau das macht den Dijkstra unnütz, weil er sich den kürzesten Weg am gesammten Gewicht des bisherigen Weges sucht. Das ist aber ein obsoleter Informationsvorsprung wenn alle Kanten dasselbe Gewicht haben und der schöne Algo wird naiv zur Breiten- bzw. Tiefensuche, weil wir alle Äste ablaufen müssen. A propos Dijkstra, sehr schöne Erklärung [manderby dijkstra] von ehm. zürcher Stud.
D.h. wir rechnen am Ende doch alles durch und cachen...

Ich empfehle wirklich @Moritz, dass Du Dich darauf beschränkst die Distanz zu berechnen. Methoden mittels Herauschlösung von Kanten findest Du [kürzester weg ungewichtet graph]. Aber das ist nicht ganz einfach und Du müsstest Sonderbehandlungen einführen, weil Dein Graph nicht zusammenhängt.

Allgemeine Algos um [Spannbäume] (auch [minimaler Spannbaum]) zu berechnen (wahrscheinlich würde ich es so probieren?) sind [Algorithmus von Kruskal] und [Algorithmus von prim]. Dabei ist der Krux aber, dass Dein Graph noch immer nicht gewichtet ist. Wg. des nicht-zusammenhängen musst Du hier wieder schauen, dass Du schnell genug abbrichst, wenn der Erfolg ausbleibt.

Was Sascha im gelinkten Post gepostet hat kann dabei nützlich sein. [bidirectional search]

D.h. mir fällt ganz ernsthaft kein Musterbuch Algorithmus ein, der Dein Problem löst. Es wäre möglich die Anzahl der Kontakte eines Mitgliedes als Kantengewicht zu benutzen, da darin naiv die Whk beschrieben ist, dass ein gesuchtes Mitglied vorkommt. Das hat den unübersehbaren Nachteil, dass dort entsprechend viele weitere Varianten zur nächsten Iteration fällig werden.

Wie sieht denn Dein Datentyp aus?

Alternativ könntest Du - ähnlich wie Google mit Blockrank - versuchen die Mitliedern in Kästchen (also in Untergruppen) einzuteilen, weil Du mit dieser Info den kürzesten Weg schneller berechnen könntest. Das hätte den Vorteil, dass man schnell nach Connectivität zw den beiden Kästchen suchen kann in denen die beiden Mitgliedern sind. Allerdings rate ich davon ab.

Hm, ich weiss wirklich nicht recht. Ich würde mich darauf beschränken die nächsten 6 Ebenen pro Mitglied zu holen (max 12. min 1 queries) und diese zu schneiden. Implementier das mal, das sollte sehr einfach sein, und dann implementierst Du Caching. Evtl. gibt es rein mathematische Lösungen....?

PS: Alles in [] bezeichnet eine Suchabfrage, d.h. Texte in eckigen Klammern sind an Google zu füttern. (Das könnte man grad in den bb Code implementieren...)

Hallo,

@Moritz: Hast Du mittlerweile eine Lösung für das Problem gefunden? Ich sitze im Moment am gleichen Projekt, sprich will die kürzesten Wege zwischen Communitymitgliedern anzeigen lassen.

Das imho größte Problem besteht hierbei darin, daß es ständig Änderungen gibt, ich also oft (am besten in Echtzeit) Updates in der Datenbasis berücksichtigen muß. Wäre da eine Adjazentenmatrix eine elegante Lösung? Sprich wie lange würde es dauern, diese aus der Datenbanktabelle zu generieren? Sollte ja eigentlich überschaubar sein (ich rechne für mein Projekt ebenfalls mit 10.000 Mitgliedern mit jeweils im Schnitt 20 Kontakten).

Als Suchalgorithmus erscheint mir eine iterative Tiefensuche (Branch-and-Bound) derzeit am besten. Was meint Ihr?

Weiß jemand zufällig, auf welche Weise das bei OpenBC realisiert wurde?

Viele Grüße...

möchte sowas auch realisieren (~10.000 member geplant)
mein bisheriger pseudocode-ansatz:

-> wie kann ich das optimieren/wie lese ich da die zwischenkontakte aus?

http://de.wikipedia.org/wiki/Algorithmus_v...yd_und_Warshall scheint auch ganz hilfreich, blicke da aber noch nicht ganz durch..

Es gibt übrigens auch ein Visualisierungswerkzeug in Java für Beziehungen:

http://www.jibble.org/piespy/
http://www.jibble.org/shakespeare/

um die hirachie des graphen zu gewähleisten, muss ich jede freundschaft auch doppelt in der datenbank anlegen,oder?
also:
id | user | freund

1 | testperson_a | testperson_b
2 | testperson_b | testperson_a