Hey guys, I need some help from all of you to try testing some algorithms. The following algorithms is used in finding friend connections. The current algorithm used in fmod 0.1.0a is the find_friend_connections() which is an implementation of Recursive Iterative deepening depth first search algorithm (recursive ITDDFS). Now I have come up with the other 3 algorithms namely breadth_first_search(), non-recursive ITDDFS, and a database union search.
You can learn more about these at
http://en.wikipedia.org/wiki/Tree_traversal
In my own benchmark, the breadth_first_search and the non-recursive ITTDFS are both fast. The non-recursive ITDDFS uses a new implementation of Depth first search which is actually a depth limiting one (and is not recursive). The database union search uses sql query to get the connection and its performance is a little slower. The current implementation - the recursive ITDDFS is 3 times slower compared to the Breadth First Search algorithm.
Take note also that if you use simulated array of friends using php array variable, the breadth first search seems to be slow compared to the ITTDFS. But on real database implementation, this is not the case.
Just post a reply here in this forum and state your benchmark test with deatails such as how many friends in the database you have and if possible you website where fmod is installed.
Also if you like to program another algorithm, feel free to do so. The only requirement is that the function shopuld be in the format function_name($uid1, $uid2) and function_name will return comma delimited list of friend. Ex. 1,3,45,23 (1&3, 3&45, 45&23 are friends)
Now to implement one of this codes, just paste the selected code in front of usercp_viewprofile.php. Then FIND $friend_conn = find_friend_connections($userdata['user_id'],$profiledata['user_id']); and replace it with the selected algorithm. Ex. $friend_conn = breadth_first_search($userdata['user_id'],$profiledata['user_id']);
Code: Select all
function breadth_first_search($bfs_uid1, $bfs_uid2)
{
global $db;
$queue = array();
$u1_friends = array();
$scanned = array();
$node = $bfs_uid1;
$sql = "SELECT *
FROM " . FRIENDS_TABLE . "
WHERE user_a = " . $bfs_uid1;
if ( !($result = $db->sql_query($sql)) )
{
message_die(GENERAL_ERROR, 'Could not query friends information', '', __LINE__, __FILE__, $sql);
}
while ( $row = $db->sql_fetchrow($result) )
{
$u1_friends[] = $row['user_b'];
$queue[] = $node . ',' . $row['user_b'];
}
$db->sql_freeresult($result);
if (in_array($bfs_uid2, $u1_friends)){
return $node . ',' . $bfs_uid2;
break;
}
$scanned[] = $bfs_uid1;
while(!empty($queue))
{
$node = array_shift($queue); // get the first element in array (FIFO)
$node2 = explode(',', $node); // the string is in format id1,id2,...idx we need idx so split first
if (count($node2)>10)
{
return '';
}
$last_id = array_pop($node2); // then pop the last...
if ($last_id==$bfs_uid2)
{
return $node;
}
$last_id_friends = array();
$sql = "SELECT *
FROM " . FRIENDS_TABLE . "
WHERE user_a = " . $last_id;
if ( !($result = $db->sql_query($sql)) )
{
message_die(GENERAL_ERROR, 'Could not query friends information', '', __LINE__, __FILE__, $sql);
}
while ( $row = $db->sql_fetchrow($result) )
{
$last_id_friends[] = $row['user_b'];
if (!in_array($row['user_b'], $scanned))
{
$queue[] = $node . ',' . $row['user_b'];
}
}
$db->sql_freeresult($result);
if (in_array($bfs_uid2, $last_id_friends)){
return $node . ',' . $bfs_uid2;
break;
}
$scanned[] = $last_id;
}
}
Code: Select all
function database_union_search($uid1, $uid2)
{
global $db;
for ($x=0; $x<10 ; $x++)
{
$left_join='';
$selects="CONCAT_WS(',' ,f0.user_a ";
for ($y=1; $y<=$x ; $y++)
{
$left_join .= "LEFT JOIN " . FRIENDS_TABLE . " f$y ON f" . strval($y-1) . ".user_b = f$y.user_a ";
$selects .= ", f$y.user_a " ;
}
$selects .= ", f$x.user_b )";
// Now, $selects will be like CONCAT_WS(',' , f0.user_, f1.user_a, f2.user_a, ... , fx.user_b)
$sql = "SELECT $selects
FROM ( " . FRIENDS_TABLE . " f0
$left_join)
WHERE f0.user_a = $uid1
AND f$x.user_b = $uid2";
if ( !($result = $db->sql_query($sql)) )
{
message_die(GENERAL_ERROR, 'Could not query friends information', '', __LINE__, __FILE__, $sql);
}
while ( $row = $db->sql_fetchrow($result) )
{
return $row[$selects];
}
$db->sql_freeresult($result);
}
}
Code: Select all
// The following two functions is needed to work together...
function nonrecursive_ITDDFS($uid1, $uid2){
for ($x=1 ; $x<=10 ; $x++){
$sr = $depth_limited_search($uid1, $uid2, $x);
if ($sr!='') { return $sr; }
}
}
function depth_limited_search($dfs_uid1, $dfs_uid2, $depth)
{
global $db;
$queue = array();
$u1_friends = array();
$scanned = array();
$node = $dfs_uid1;
$sql = "SELECT *
FROM " . FRIENDS_TABLE . "
WHERE user_a = " . $dfs_uid1;
if ( !($result = $db->sql_query($sql)) )
{
message_die(GENERAL_ERROR, 'Could not query friends information', '', __LINE__, __FILE__, $sql);
}
while ( $row = $db->sql_fetchrow($result) )
{
$u1_friends[] = $row['user_b'];
$queue[] = $node . ',' . $row['user_b'];
}
$db->sql_freeresult($result);
if (in_array($dfs_uid2, $u1_friends)){
return $node . ',' . $dfs_uid2;
break;
}
$scanned[] = $dfs_uid1;
while(!empty($queue))
{
$node = array_pop($queue); // get the last element in array (LIFO)
$node2 = explode(',', $node); // the string is in format id1,id2,...idx we need idx so split first
if (count($node2)>$depth)
{
return '';
}
$last_id = array_pop($node2); // then pop the last...
if ($last_id==$dfs_uid2)
{
return $node;
}
$last_id_friends = array();
$sql = "SELECT *
FROM " . FRIENDS_TABLE . "
WHERE user_a = " . $last_id;
if ( !($result = $db->sql_query($sql)) )
{
message_die(GENERAL_ERROR, 'Could not query friends information', '', __LINE__, __FILE__, $sql);
}
while ( $row = $db->sql_fetchrow($result) )
{
$last_id_friends[] = $row['user_b'];
if (!in_array($row['user_b'], $scanned))
{
$queue[] = $node . ',' . $row['user_b'];
}
}
$db->sql_freeresult($result);
if (in_array($dfs_uid2, $last_id_friends)){
return $node . ',' . $dfs_uid2;
break;
}
$scanned[] = $last_id;
}
}
