9

I run my own website where people have the ability to have friends. This is how I store friendships:

id1 | id2
 1  |  2
 1  |  3
 2  |  4

Basically user id 1 is friends with user id 2 and id 3 and user 2 is friends user id 4.

What I'm trying to get is how, for example, are 1 and 4 connected. Currently it's like that:

1 -> 2 -> 4

If it's about between 4 and 3 it would be:

4 -> 2 -> 1 -> 3

The idea is to find as quick link between those two as possible

The only way I can think about is creating a massive big loop with a lots of loops and stuff like that which probably can be better and more efficient.

4
  • 5
    sounds like a variation on traveling salesman?
    – KevinDTimm
    Mar 12, 2013 at 17:23
  • 3
    This is non-trivial. Look into graph theory.
    – engineerC
    Mar 12, 2013 at 17:30
  • 1
    Roughly how many entries do you have in the friendships table? What is the density of the graph, i.e., most people have a couple of friends, or most people have hundreds of friends? Is it required that you find the absolute shortest path, or any path is ok? Do you want to find the path no matter how long it is, or can you stop for instance at 5 links max? Is id1 always less than id2?
    – mellamokb
    Mar 12, 2013 at 18:18
  • I will look into the graph theory @mellamokb I do not know how many entries there are, but probably over 5000. There's a guy who has 2496. id1 is not necessery less than id2, basically id1 is the guy who requested the friendship. Well basically the shortest path is the best and the point is to make it without a limit, because else I think I can make it with some nested queries
    – Nikola
    Mar 12, 2013 at 22:28

5 Answers 5

3

RDBMS is not good at doing stuff like this.

What you need is a graph db, and I strongly recommend Neo4j, which is popular and open sourced.

1

Shortest friendship path is usually found by using an algorithm called two-way search. Thw main idea is to look at network of friendships as an undirected graph, where you are seeking the shortest path between 2 nodes. This mentioned algorithm starts searching from both nodes at the same time, discover neighbour nodes of the already known ones. When the two surfaces of known nodes first overlap, than a the shortest path is found.

Please note that certain special cases needed to be handled, such as when one of the people is in an "island" at the graph, such a node set that is not connected to other nodes (think of a community with no relationship to thw outside world)

Bottom line it is a not-so-big while loop.

1

What I would try first is a breadth-first search.

Note that the following code will not work without modifications because I haven't even checked for syntax errors. The query() function should return a list of entries as you see. It's intended to give you an idea.

/* Return one of the shortest friendship paths from f1 to f2. Returns false when
 * path is longer than limit or no path exists. 
 * PROTOTYPE FIX IT YOURSELF
 */
function friend_path($f1, $f2, $limit) {
    $friended = array($f1 => false); // The tree of friendships leading to f1
    $discovered_friends = array($f1); // List of friends to examine next
    while($limit-- > 0) {
        $interesting_friends = $discovered_friends;
        $discovered_friends = array();
        foreach(query("
            SELECT id1 AS friender, id2 AS friendee  
            FROM friendships 
            WHERE id1 in (".join(',', $interesting_friends).")
            ") as $discovered_link
        ) {
            $friendee = $discovered_link['friendee'];
            $friender = $discovered_link['friender'];
            if (!isset($friended[$friendee])) {
                $discovered_friends []= $friendee;
                $friended[$friendee] = $friender;
                if ($friendee == $f2) {
                    return friend_path_track($friended, $friendee, $track);
                }
            }
        }
        if (count($discovered_friends) < 1) return false;
    }
    return false;
}

function friend_path_track($friended, $friendee, $track) {
    $track []= $friendee;
    if ($friended[$friendee]) === false) return array_reverse($track);
    return friend_path_track($friended, $friended[$friendee], $track);
}

This code was optimized for simplicity. For anything but toy databases, you should be doing a bidirectional search where you keep two lists, friended and friends (the tree of frienders to f2). You'd be extending the list which is shorter, while looking for a match in the other list. You can't trick complexity though, so you'll have to keep the limit on iterations very low unelss you like the sound of trashing servers.

0

It is best to do a breadth-first search in both directions i.e from both individuals in question and stop this process when you find a connection or reach the specified depth limit. The idea is also to reach the more popular individuals first (while performing BFS)

0

This would be with edges having a weight of 1. There is a sample code to calculate connection between 2 friends in a social network in PHP

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.