Ruby on Rails

Ruby on Rails

This thread has been closed so unfortunately you can't post here any more.

Posts 1-9 of 9
  • Post visible to registered members
  • Max Jonas Werner
    Max Jonas Werner
    The company name is only visible to registered members.
    Re: FoaF - Friend of a Friend -- Wie realisieren? Ansätze?
    Hallo Stefan,

    eine konkrete Lösung kann ich dir nicht liefern, aber einen Ansatz: Deine Frage zielt ja eher grundsätzlich auf die Implementierung des FoaF-Features an. Für die Berechnung eines Pfades von einem User zu einem anderen musst du das Netzwerk als Graph behandeln und einen generischen Algorithmus wie Dijkstras Algorithmus zur Berechnung des kürzesten Pfades anwenden. Rails bietet da meines Erachtens keine direkte Unterstützung.

    HTH,
    Max
    • 23 Dec 2007, 10:16 am
  • Post visible to registered members
  • Post visible to registered members
  • Tilman Moser
    Tilman Moser    Premium Member
    The company name is only visible to registered members.
    Re^3: FoaF - Friend of a Friend -- Wie realisieren? Ansätze?
    Hallo allerseits,

    meine Antwort in Kürze, weil Zeitmangel, dafür mit konkreter Lösung.

    Richtig: Es handelt sich hierbei um einen Graph.

    Falsch: Dijkstras Algorithmus ist dafür ungeeignet, da es sich
    a) nicht um einen gewichteten Graph handelt (wir wollen uns ja nicht anmaßen zu entscheiden wie dick zwei Menschen miteinander befreundet sind und haben es damit mit Vektoren der fixen Länge 1 zu tun),
    b) wir nicht nur nach dem kürzesten Weg suchen und
    c) der Algorithmus, den wir brauchen, eigentlich Tiefensuche heißt.

    Da die Tiefensuche kein optimaler Algo ist und wir egal ob Skriptsprache oder kompilierte Hochsprache unseren Server nicht mit unnötigen Rechenoperatoren stressen wollen (glaubt mir, ich habe es ausprobiert die Tiefensuche in einer Skriptsprache zu implementieren und es dauert inakzeptabel lang), überlassen wir diese holde Aufgabe einem darauf spezialisiertem Werkzeug: unserer Datenbank. Denn die kann dank optimierter Algorithmen und Caching hervorragend damit umgehen und dafür lieben wir sie.

    Der nachfolgende Code ist in PHP geschrieben (da es eigentlich nur 2 Funktionen sind, denke ich, dass man diese leicht in ruby übertragen kann, sofern man das Konzept verstanden hat) und benötigt für eine Suche von maximal hundert Pfaden zwischen A und B über maximal 5 Zwischenknoten ganze läppische 0,3 Sekunden und zeigt freundlicherweise die kürzesten Wege zuerst an.
    Für maximal 1000 Pfade bewegen wir uns bei gerade noch akzeptablen ca. 2,3 Sekunden, 10000 Pfade brauchen dann doch ca. 25 Sekunden. Aber bei der Datenmenge sollte man sich eher Gedanken über die Übertragungszeit zwischen Server und Client-Browser machen.

    So, hier nun das Skript:

    #!/usr/bin/php
    <?
    /*
    * socialgraph.php
    *
    * Copyright 2008 Tilman Moser <moser@w3-dev.de>
    *
    * This program is free software; you can redistribute it and/or modify
    * it under the terms of the GNU General Public License as published by
    * the Free Software Foundation; either version 2 of the License, or
    * (at your option) any later version.
    *
    * This program is distributed in the hope that it will be useful,
    * but WITHOUT ANY WARRANTY; without even the implied warranty of
    * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    * GNU General Public License for more details.
    *
    * You should have received a copy of the GNU General Public License
    * along with this program; if not, write to the Free Software
    * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
    * MA 02110-1301, USA.
    */

    /* DATABASE SETUP:

    CREATE TABLE `links` (
    `id` int(11) NOT NULL auto_increment,
    `a` int(11) default NULL,
    `b` int(11) default NULL,
    PRIMARY KEY (`id`),
    UNIQUE KEY `connection` (`a`,`b`)
    ) ENGINE=MyISAM AUTO_INCREMENT=11917190 DEFAULT CHARSET=latin1

    */

    function find_links($a,$b,$maxpaths=100,$maxdepth=5) {
    global $db;
    $found = 0; $paths = array();
    for ($i=0; $i<=$maxdepth; $i++) {
    $query = getQuery($a,$b,$i,$maxpaths-$found);
    echo "Tiefe $i: $query\n\n"; // nur Demo
    $rs = $db->query($query);
    if ($rs->num_rows) {
    $found += $rs->num_rows;
    while ($row = $rs->fetch_row())
    $paths[] = join(" >> ", $row);
    }
    }
    return $paths;
    }

    function getQuery($from,$to,$depth,$max) {
    $q_select = "SELECT l0.a,l0.b";
    $q_from = "FROM links l0";
    $q_where = "WHERE l0.a=$from";
    for ($i=0,$j=1; $i<$depth; $i++,$j++) {
    $q_select.=",l$j.b";
    $q_from.=" join links l$j on l$i.b = l$j.a";
    for ($k=0; $k<$j; $k++)
    $q_where.= " AND l$j.b != l$k.a";
    }
    $q_where .= " AND l$i.b=$to LIMIT $max";
    return "$q_select $q_from $q_where";
    }



    /* SETTINGS */
    $user = 10000; $contacts = 50; $maxpaths = 1000; $maxdepth = 5;

    $db = new mysqli('localhost', 'development', NULL, 'socialgraph');
    /* check connection */
    if (mysqli_connect_errno()) {
    printf("Connect failed: %s\n", mysqli_connect_error());
    exit();
    }

    /* FILL DATABASE WITH RANDOM DATA:

    $db->query("TRUNCATE TABLE links");
    $stmt_insert = $db->prepare("INSERT INTO links(a,b) VALUES(?,?)");
    for ($a=1; $a<=5000; $a++) {
    for ($i=1; $i<20; $i++) {
    $b = rand(1,5000);
    if ($a != $b) {
    $stmt_insert->bind_param("dd", $a, $b);
    $stmt_insert->execute();
    $stmt_insert->bind_param("dd", $b, $a);
    $stmt_insert->execute();
    }
    }
    }

    */

    // FIND DEMO:
    $t0 = microtime(true);
    $paths = find_links(rand(1,$user), rand(1,$user), $maxpaths, $maxdepth);
    $t1 = abs(microtime(true) - $t0);
    print_r($paths);
    echo $t1."\n";

    $db->close();

    /* OUTPUT:

    Tiefe 0: SELECT l0.a,l0.b FROM links l0 WHERE l0.a=3803 AND l0.b=707 LIMIT 100

    Tiefe 1: SELECT l0.a,l0.b,l1.b FROM links l0 join links l1 on l0.b = l1.a WHERE l0.a=3803 AND l1.b != l0.a AND l1.b=707 LIMIT 100

    Tiefe 2: SELECT l0.a,l0.b,l1.b,l2.b FROM links l0 join links l1 on l0.b = l1.a join links l2 on l1.b = l2.a WHERE l0.a=3803 AND l1.b != l0.a AND l2.b != l0.a AND l2.b != l1.a AND l2.b=707 LIMIT 100

    Tiefe 3: SELECT l0.a,l0.b,l1.b,l2.b,l3.b FROM links l0 join links l1 on l0.b = l1.a join links l2 on l1.b = l2.a join links l3 on l2.b = l3.a WHERE l0.a=3803 AND l1.b != l0.a AND l2.b != l0.a AND l2.b != l1.a AND l3.b != l0.a AND l3.b != l1.a AND l3.b != l2.a AND l3.b=707 LIMIT 23

    Tiefe 4: SELECT l0.a,l0.b,l1.b,l2.b,l3.b,l4.b FROM links l0 join links l1 on l0.b = l1.a join links l2 on l1.b = l2.a join links l3 on l2.b = l3.a join links l4 on l3.b = l4.a WHERE l0.a=3803 AND l1.b != l0.a AND l2.b != l0.a AND l2.b != l1.a AND l3.b != l0.a AND l3.b != l1.a AND l3.b != l2.a AND l4.b != l0.a AND l4.b != l1.a AND l4.b != l2.a AND l4.b != l3.a AND l4.b=707 LIMIT 0

    Tiefe 5: SELECT l0.a,l0.b,l1.b,l2.b,l3.b,l4.b,l5.b FROM links l0 join links l1 on l0.b = l1.a join links l2 on l1.b = l2.a join links l3 on l2.b = l3.a join links l4 on l3.b = l4.a join links l5 on l4.b = l5.a WHERE l0.a=3803 AND l1.b != l0.a AND l2.b != l0.a AND l2.b != l1.a AND l3.b != l0.a AND l3.b != l1.a AND l3.b != l2.a AND l4.b != l0.a AND l4.b != l1.a AND l4.b != l2.a AND l4.b != l3.a AND l5.b != l0.a AND l5.b != l1.a AND l5.b != l2.a AND l5.b != l3.a AND l5.b != l4.a AND l5.b=707 LIMIT 0

    Array
    (
    [0] => 3803 >> 51 >> 5979 >> 707
    [1] => 3803 >> 112 >> 6431 >> 707
    [2] => 3803 >> 290 >> 8551 >> 707
    [3] => 3803 >> 742 >> 563 >> 707
    [4] => 3803 >> 1088 >> 1725 >> 707
    [5] => 3803 >> 1213 >> 3746 >> 707
    [6] => 3803 >> 1441 >> 5234 >> 707
    [7] => 3803 >> 1849 >> 3746 >> 707
    [8] => 3803 >> 2042 >> 7886 >> 707
    [9] => 3803 >> 2296 >> 8846 >> 707
    [10] => 3803 >> 2752 >> 5306 >> 707
    [11] => 3803 >> 2752 >> 8474 >> 707
    [12] => 3803 >> 3010 >> 1387 >> 707
    [13] => 3803 >> 3090 >> 3525 >> 707
    [14] => 3803 >> 3201 >> 67 >> 707
    [15] => 3803 >> 3201 >> 4397 >> 707
    [16] => 3803 >> 3203 >> 3459 >> 707
    [17] => 3803 >> 3978 >> 4728 >> 707
    [18] => 3803 >> 4063 >> 1387 >> 707
    [19] => 3803 >> 4063 >> 5156 >> 707
    [20] => 3803 >> 4134 >> 7219 >> 707
    [21] => 3803 >> 4142 >> 563 >> 707
    [22] => 3803 >> 4142 >> 9541 >> 707
    [23] => 3803 >> 4406 >> 5202 >> 707
    [24] => 3803 >> 4789 >> 3159 >> 707
    [25] => 3803 >> 4946 >> 9769 >> 707
    [26] => 3803 >> 5131 >> 6431 >> 707
    [27] => 3803 >> 5131 >> 9769 >> 707
    [28] => 3803 >> 5238 >> 2562 >> 707
    [29] => 3803 >> 5504 >> 957 >> 707
    [30] => 3803 >> 5504 >> 9704 >> 707
    [31] => 3803 >> 5983 >> 9704 >> 707
    [32] => 3803 >> 6066 >> 96 >> 707
    [33] => 3803 >> 6191 >> 9769 >> 707
    [34] => 3803 >> 6283 >> 7886 >> 707
    [35] => 3803 >> 6314 >> 1470 >> 707
    [36] => 3803 >> 6572 >> 6882 >> 707
    [37] => 3803 >> 6572 >> 8846 >> 707
    [38] => 3803 >> 6722 >> 3945 >> 707
    [39] => 3803 >> 6722 >> 9699 >> 707
    [40] => 3803 >> 6848 >> 4676 >> 707
    [41] => 3803 >> 6963 >> 6119 >> 707
    [42] => 3803 >> 7011 >> 3159 >> 707
    [43] => 3803 >> 7079 >> 4424 >> 707
    [44] => 3803 >> 7079 >> 8752 >> 707
    [45] => 3803 >> 7100 >> 3159 >> 707
    [46] => 3803 >> 7140 >> 4397 >> 707
    [47] => 3803 >> 7465 >> 7117 >> 707
    [48] => 3803 >> 7507 >> 5234 >> 707
    [49] => 3803 >> 7888 >> 3001 >> 707
    [50] => 3803 >> 7977 >> 11 >> 707
    [51] => 3803 >> 8146 >> 5031 >> 707
    [52] => 3803 >> 8146 >> 6431 >> 707
    [53] => 3803 >> 8168 >> 1016 >> 707
    [54] => 3803 >> 8168 >> 1283 >> 707
    [55] => 3803 >> 8168 >> 9843 >> 707
    [56] => 3803 >> 8208 >> 96 >> 707
    [57] => 3803 >> 8208 >> 161 >> 707
    [58] => 3803 >> 8221 >> 3746 >> 707
    [59] => 3803 >> 8242 >> 1394 >> 707
    [60] => 3803 >> 8887 >> 5031 >> 707
    [61] => 3803 >> 9037 >> 2754 >> 707
    [62] => 3803 >> 9042 >> 6119 >> 707
    [63] => 3803 >> 9135 >> 7886 >> 707
    [64] => 3803 >> 9135 >> 9061 >> 707
    [65] => 3803 >> 9192 >> 1283 >> 707
    [66] => 3803 >> 9256 >> 1470 >> 707
    [67] => 3803 >> 9604 >> 8482 >> 707
    [68] => 3803 >> 9715 >> 6578 >> 707
    [69] => 3803 >> 9735 >> 788 >> 707
    [70] => 3803 >> 9735 >> 9699 >> 707
    [71] => 3803 >> 9739 >> 3001 >> 707
    [72] => 3803 >> 9739 >> 5202 >> 707
    [73] => 3803 >> 9776 >> 9541 >> 707
    [74] => 3803 >> 9787 >> 96 >> 707
    [75] => 3803 >> 9787 >> 2074 >> 707
    [76] => 3803 >> 9787 >> 4728 >> 707
    [77] => 3803 >> 51 >> 18 >> 11 >> 707
    [78] => 3803 >> 51 >> 220 >> 4346 >> 707
    [79] => 3803 >> 51 >> 584 >> 7219 >> 707
    [80] => 3803 >> 51 >> 628 >> 9843 >> 707
    [81] => 3803 >> 51 >> 1574 >> 6119 >> 707
    [82] => 3803 >> 51 >> 1682 >> 4424 >> 707
    [83] => 3803 >> 51 >> 1747 >> 2053 >> 707
    [84] => 3803 >> 51 >> 1855 >> 8843 >> 707
    [85] => 3803 >> 51 >> 1929 >> 161 >> 707
    [86] => 3803 >> 51 >> 2116 >> 6316 >> 707
    [87] => 3803 >> 51 >> 2116 >> 7886 >> 707
    [88] => 3803 >> 51 >> 2172 >> 6325 >> 707
    [89] => 3803 >> 51 >> 2342 >> 4346 >> 707
    [90] => 3803 >> 51 >> 2831 >> 2053 >> 707
    [91] => 3803 >> 51 >> 2831 >> 3335 >> 707
    [92] => 3803 >> 51 >> 2832 >> 6431 >> 707
    [93] => 3803 >> 51 >> 3029 >> 9587 >> 707
    [94] => 3803 >> 51 >> 3062 >> 1872 >> 707
    [95] => 3803 >> 51 >> 3157 >> 6603 >> 707
    [96] => 3803 >> 51 >> 3201 >> 67 >> 707
    [97] => 3803 >> 51 >> 3201 >> 4397 >> 707
    [98] => 3803 >> 51 >> 3301 >> 6882 >> 707
    [99] => 3803 >> 51 >> 3617 >> 4194 >> 707
    )
    0.341516971588

    */
    ?>
    • 12 Jan 2008, 5:26 pm
  • Post visible to registered members
  • Post visible to registered members
  • Tilman Moser
    Tilman Moser    Premium Member
    The company name is only visible to registered members.
    Re^6: FoaF - Friend of a Friend -- Wie realisieren? Ansätze?
    Hallo Stefan,

    (du ist denke ich beiderseitig ok :)

    die Relationen sind bei mir ebenfalls ungerichtet angelegt, siehe:

    $stmt_insert->bind_param("dd", $a, $b);
    $stmt_insert->execute();
    $stmt_insert->bind_param("dd", $b, $a);
    $stmt_insert->execute();

    Ein distinct ist eigentlich nicht nötig, da der pfad so ausschaut:

    R1.a = START
    R1.b join auf R2.a
    R2.a join auf R3.b
    ...
    Rn.b = END

    zudem wird ausgeschlossen, dass ein Wert doppelt vorkommt.

    Bei gerichteten Relationen (ohne doppelte Speicherung) kann der Algo nicht funktionieren :)
    This post was modified on 19 Jan 2008 at 06:13 pm.
    • 19 Jan 2008, 6:12 pm
  • User photo
    Wolfgang Tiefenseher
    (not a XING member)
    Re^4: FoaF - Friend of a Friend -- Wie realisieren? Ansätze?
    interessant, aber wird der SocialGraph heutzutage nicht überschätzt?
    fehlt da nicht - um mit TimBl zu sprechen - nicht erst noch das globale WebOfTrust?
    • 01 Apr 2009, 05:53 am