Social networking sites are coming up daily. Users are linked to other users based on various factors like friends, interests, groups, same school, same company, same locality and many more. In all these we are connected to people we know or upto next level that is friends of friends. A need has been identified to find connections between two users, how we are linked to another user. A concept similar to 6 degrees of separation.
Below is the code and algorithm in PHP to find connection and smallest path between two users in a social path. This is based on friendship. Find friends, their friends and so on and reaching to the user. This code shows the path as well to the user being searched if found successfully. In this code, 6 level/depth/degrees is being searched which can be changed. Also, maximum number of users/friends (overall friends) to refer/identify can be defined so as to make only limited set of iterations.
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();
[/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>$user_find</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_level[$level_now][]=$user_from;
//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
//getting parent node. For source node it is taken as source node itself
if($user_from==$node_now)
{
$node_now_parent=$node_now;
}
else
{
$node_now_parent=$list_parents[$node_now];
}
//find level for a node
$sts_found_node_level=0;
$node_level_now=0;
$sts_found_node=0;
while($sts_found_node!=1)
{
//getting depth level of current node based on depth of parent node and incrementing it
if(in_array($node_now_parent,$list_level[$node_level_now]))
{
$sts_found_node_level=1;
$sts_found_node=1;
}
else
{
$node_level_now++;
if($node_level_now>$level_max)
{
$sts_found_node=1;
}
}
}
if($sts_found_node_level==0)
{
echo "There is some issue. Not able to proceed<br>"; //an error message if depth level is not found. Some issue with data or algorithm
}
else
{
//Incrementing depth for current node. Keeping it same for source node.
$level_now=$node_level_now;
if($user_from==$node_now)
{
$level_next=$level_now;
}
else
{
$level_next=$level_now+1;
}
//inserting current node in depth array. It is used to track depth level/degrees.
if(isset($list_level[$level_next]))
{
if(in_array($node_now,$list_level[$level_next]))
{
}
else
{
$list_level[$level_next][]=$node_now;
}
}
else
{
$list_level[$level_next][]=$node_now;
}
//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(in_array($pal_now,$list_done))
{
}
else
{
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))
{
//do nothing if current friend is already in Todo List
}
else
{
//adding friend in ToDo list. Also assigning friend as child
$list_todo[]=$pal_now;
$list_parents[$pal_now]=$node_now;
}
}
}
}
}
}
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>";
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_rev>0)
{
echo "<div>";
echo implode(" > ", $parent_chain_rev);
echo "</div>";
}
}
}
}
echo "</div>";
[/php]