This is the second version of our earlier post Find connection path between two users in a social network using PHP. In this version performance issues have been taken care upto some level along with minor tweaks to code to make it more efficient.
Initialising start user, end user, maximum level/degree/depth
[php]
$user_from=1; //start user (node)
$user_find=10; //end user (node)
$level_max=6;
$sts_found=0;
$list_todo=array();
$list_done=array();
$list_parents=array();
$list_pals=array();
$list_depth=array();
[/php]
Database table structure explained
[php]
//database table structure
//table name: pals
//column names: pal_id,pal_act,pal_sts,pal_usrid,pal_usrid_by
//table data logic: pal_act, pal_sts should be 1; pal_usrid is the user to which request is sent; pal_usrid_by is the user by whom request is sent. User/pal/node can be either in pal_usrid or pal_usrid_by.
[/php]
Function to get Pals/friends list for each node
[php]
function get_pals($usrid)
{
$qry_pals="SELECT * FROM pals WHERE pal_act=’1′ AND pal_sts=’1′ AND (pal_usrid=’$usrid’ OR pal_usrid_by=’$usrid’)";
$rsl_pals=mysql_query($qry_pals);
$n_pals = mysql_num_rows($rsl_pals);
$list_pals=array();
if($n_pals!=0)
{
for($i=0;$i<$n_pals;$i++)
{
$arr_pals = mysql_fetch_row($rsl_pals);
$pal_usrid=$arr_pals[3];
$pal_usrid_by=$arr_pals[4];
if($pal_usrid_by==$usrid)
{
$pal_usrid_to=$pal_usrid;
}
else
{
$pal_usrid_to=$pal_usrid_by;
}
$list_pals[]=$pal_usrid_to;
}
}
return($list_pals);
}
[/php]
Main Code, looking for destination node/friend
[php]
echo "<div>Looking for Connection between <b>$v_usr_prf_link</b> and <b>You</b> within <b>$level_max degrees</b></div>";
$list_todo[]=$user_from; //adding starting node/user
$loop_count_max=100; //use this if you want to stop searching after certain number of nodes have been examined it should be around 10000
$loop_count=0;
$level_now=0;
$list_depth[$user_from]=$level_now;
//Finding desnitation node/user
while(count($list_todo)!=0)
{
$loop_count++; //if loop count is being used
$list_pals=array(); //intialising friends list for each loop
$node_now=array_shift($list_todo); //current node/child
$list_done[]=$node_now; //adding list of current node as done
$level_now=$list_depth[$node_now];
$level_next=$level_now+1;
//Validating if current loop is going within maximum degree
if($level_next<$level_max)
{
$list_pals=get_pals($node_now);//Getting Friends
if(count($list_pals)>0)
{
foreach($list_pals AS $list_pals_val)
{
$pal_now=$list_pals_val;
//checking if exists in Done/processed list
if(!isset($list_done[$pal_now]))
{
//$list_done[]=$node_now;
if($pal_now==$user_find)
{
//If source is found.
$sts_found=1; //setting success status to 1
$list_todo=array(); //to end while loop
$list_parents[$user_find]=$node_now; //adding current node to backtrack path
}
else
{
if(!in_array($pal_now,$list_todo))
{
//adding friend in ToDo list. Also assigning friend as child
$list_todo[]=$pal_now;
$list_parents[$pal_now]=$node_now;
$list_depth[$pal_now]=$level_next;
}
}
}
}
}
}
else
{
//for exiting from main while loop when maximum depth/degrees is reached
$list_todo=array();
}
//for exiting from main while loop when maximum number of loop count reached. For system efficiency loop is used.
if($loop_count>$loop_count_max)
{
$list_todo=array();
}
}
[/php]
Output path if destination user/node found
[php]
//Output path if found.
echo "<div>";
if($sts_found==0)
{
//If not found within depth/degrees and loop count
echo "<div style=’font-weight:bold;color:#ff0000;’>No Connection found</div>";
}
else
{
//if found
echo "<div style=’font-weight:bold;color:#00ff00;’>Connection found</div>";
if(count($list_parents)>0)
{
$grandparent=$user_from;//source node
$parent_chain=array();
$child=$user_find;
//backtracking the path
while($child!=$grandparent)
{
$key=$list_parents[$child];
//echo "$key <br>";
$parent_chain[]=$key;
$child=$key;
//$loop_count++;
}
$count_parent_chain=count($parent_chain);
echo "<div style=’color:#0000ff; margin:10px;’>Linked with $count_parent_chain degree(s) as:</div>";
$parent_chain_dtls=array();
if($count_parent_chain>0)
{
$parent_chain_rev = array_reverse($parent_chain); //array is reveresed to get path
$parent_chain_rev[]=$user_find;//adding destination node to array
if($parent_chain_dtls>0)
{
echo "<div>";
echo implode(" > ", $parent_chain_dtls);
echo "</div>";
}
}
}
}
echo "</div>";
[/php]