This is the version (2.0) of our earlier post Find connection path between two users in a social network using PHP and http://blog.kunals.com/php-code-find-2-users-connected-friends-social-network/. In this version bidirectional search is performed from both ends/nodes/users and if found path is displayed.
This is based on graph traversal, breadth first search (bfs), bi-directional bfs. Nodes are the users and edges are considered as link between two users i.e. friendship with weight 1.
[php]
<?php
//bfs algorithm
$user_from=1; //start user (node)
$user_find=10; //end user (node)
$level_max=6;
$sts_found=0;
$list_parents=array();
$list_pals=array();
$list_depth=array();
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);
}
$list_todo[0][]=$user_from; //adding starting node/user
$list_todo[1][]=$user_find;
$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_max=100;
$loop_count=0;
$node_level_now=0;
$loop_level_now=0;
$dir=0;
$diro=1;
$dir_level_now[0]=0;
$dir_level_now[1]=0;
$dir_level_total=$dir_level_now[0]+$dir_level_now[1];
$list_depth[$user_from]=$node_level_now;
$list_depth[$user_find]=$node_level_now;
//Finding desnitation node/user
while(count($list_todo[$dir])!=0)
{
$loop_count++; //if loop count is being used
$list_pals=array(); //intialising friends list for each loop
$node_now = reset($list_todo[$dir]);
//dir
$node_level_now=$list_depth[$node_now];
if($loop_level_now!=$node_level_now)
{
$diro=$dir;
$dir=($dir+1)%2;
if($dir==0)
{
$loop_level_now=$loop_level_now+1;
}
$dir_level_now[$dir]=$loop_level_now;
$dir_level_total=$dir_level_now[0]+$dir_level_now[1]+1;
}
$node_now=array_shift($list_todo[$dir]); //current node/child
$list_done[$dir][$node_now]=1; //adding list of current node as done
$node_level_now=$list_depth[$node_now];
$node_level_next=$node_level_now+1;
$level_now=$list_depth[$node_now];
$level_next=$level_now+1;
//Validating if current loop is going within maximum degree
if($dir_level_total<$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[$dir][$pal_now]))
{
if(in_array($pal_now,$list_todo[$diro]))
{
//If source is found.
$sts_found=1; //setting success status to 1
$list_todo[$dir]=array(); //to end while loop
//$list_parents[$pal_now]=$node_now; //adding current node to backtrack path
$link_node=$pal_now;
$link_node_parent=$node_now;
}
else
{
if(!in_array($pal_now,$list_todo[$dir]))
{
//adding friend in ToDo list. Also assigning friend as child
$list_todo[$dir][]=$pal_now;
$list_parents[$pal_now]=$node_now;
$list_depth[$pal_now]=$node_level_next;
}
}
}
}
}
}
else
{
//for exiting from main while loop when maximum depth/degrees is reached
$list_todo[$dir]=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[$dir]=array();
}
}
//
echo "<div>";
if($sts_found==0)
{
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)
{
//dir 0
$grandparent=$user_from;//source node
$child=$link_node;
if($dir==0)
{
$child=$link_node_parent;
$parent_chain[0][]=$child;
}
else
{
$parent_chain[0][]=$child;
}
//backtracking the path
while($child!=$grandparent)
{
$key=$list_parents[$child];
$parent_chain[0][]=$key;
$child=$key;
}
//dir 1
$grandparent=$user_find;//source node
$child=$link_node;
if($dir==1)
{
$child=$link_node_parent;
$parent_chain[1][]=$child;
}
else
{
$parent_chain[1][]=$child;
}
//backtracking the path
while($child!=$grandparent)
{
$key=$list_parents[$child];
$parent_chain[1][]=$key;
$child=$key;
}
$count_parent_chain[0]=count($parent_chain[0]);
$count_parent_chain[1]=count($parent_chain[1]);
$count_parent_chain=$count_parent_chain[0]+$count_parent_chain[1]-1;
echo "<div style=’color:#0000ff; margin:10px;’>Linked with $count_parent_chain ".$count_parent_chain[0]. $count_parent_chain[1]." degree(s) as:</div>";
if($count_parent_chain>0)
{
$parent_chain_0_rev = array_reverse($parent_chain[0]);
$parent_chains=array_merge($parent_chain_0_rev,$parent_chain[1]);
echo "<div>";
echo implode(" > ", $parent_chains);
echo "</div>";
}
}
}
echo "</div>";
?>
[/php]