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.
id1
always less thanid2
?