Freundesnetzwerk

laticon1985

Hallo,

also ich hab ein Problem.
Ich versuche es ma irgendwie so genau wie möglich zu beschreiben.

Es geht um ein Freundesnetzwerk.

Und zwar habe ich ganz viele User und deren IDs

z.b.
peter ID51
susi ID64
alex ID33

naja und

peter ist mit susi befreundet
und alex ist auch mit susi befreundet.

wenn peter jetzt auf dem knopf klickt

sieht er das es eine verbindung zu alex gibt
nämlich über susi.

das problem ist das bei 20.000 usern oder mehr
vorkommen kann das man über 6 ecken oder mehr mit einen user verbundne ist
und das es dann ziemlich langsam wird wenn man damit die datenbank füllt.

und eine Freundschaft besteht immer aus zwei IDs

Die von mir und die vom Freund.
Der Freund hat z.b im oberen fall noch ne ID in seiner datenbank nämloich zu den anderen user alex.

So mein Proiblem ist ich weiß nicht wie ich das machen soll.
Hab ma so rum geschaut und es soll lösungen geben mit ner binär Matrix.
Aber ich habe ne absolute blockade und kommt nicht weiter
Oder vielleicht nen Programm in verbindung mit ner datenbank, wo ich glaube das ich um eine datenbank eh nicht rum komme.

Also ich hoffe ich konnte euch das so einigermaßen verständlich rüber bringen.
Und ihr könnt mir helfen.

Ich danke euch jetzt schon ganz dolle das ihr mein Text liest
und mir evtl. helfen könnt.

Ich werde euch dann das Projekt auch vorstellen wenn es fertig ist.

Mfg Lati^^

PS.: Sorry für Schreibfehler

rüdiger

Stichwort Graphentheorie

(ist aber kein C spezifisches Problem)

laticon1985

ey danke
ich werds mir ma durchlesen
kann damit bestimmt was anfangen

Ich schiebs mal nach Rund um die Programmierung. Falls es dann zu C-technisch wird, kanns der rüdiger ja wieder zurückschieben.

C++ Forumbot

Dieser Thread wurde von Moderator/in TactX aus dem Forum ANSI C in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

laticon1985

o.k.

vielleicht gibt es dann ja noch mehr lösungen und hilfen

finix

Schau dir mal Union-Find an.

hustbaer

@OP: was willste denn wissen? also welche abfrage(n) soll(en) schnell laufen?
die kürzeste verbindung zwischen A und B (falls eine existiert)? oder alle verbindungen?
mit einer datenbank lässt sich die erste frage sehr sehr einfach beantworten, und u.u. auch in akzeptabler zeit -- vorausgesetzt du zählst nur die "hops" und gewichtest nicht nach "wie gut" irgendwer mit wem anderen "befreundet" ist.
allerdings bin ich mir fast sicher dass es noch schnellere lösungen geben müsste, bzw. dass man ggf. einen spezialisierten index verwenden können müsste.

Michael E.

Wenn nach dem schnellsten Weg gefragt ist, schau dir mal das hier an: http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo7.php

Mit diesem Algo findest Du den kürzesten Pfad zw 2 Punkten:
http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra
http://computer.howstuffworks.com/routing-algorithm3.htm

Zu Deiner Frage "Wie Du das machen kannst" würde ich Dir eine Datenbank empfehlen wenn Du Mehrbenutzerbetrieb zulassen willst. Ansonsten tuen es CSV und XML auch. Beim Programmstart könntest Du dann alles in den Speicher laden. Wenn man es als 2D Array macht wären das 20.000^2 = 400.000.000 Einträge. Bei 20.000 könntest Du noch "unsigned short int" benutzen. Obergrenze ist bei 65.000, benötigt 2 Byte Platz. Außerdem brauchst Du einen Entfernungszähler +2Bytes (Freundschaften werden nicht gewichtet?) und einen Tag um den Knoten zu markieren. Diesen könnte man aber in den Entfernungszähler integrieren. Also mindestens 1,6 GB Speicher. Wieviel Ram hast Du? Wie oft errechnest Du Entfernungen? Wieviel Zeit darf der Algo in Asnpruch nehmen?