Recursive function help...

silent · Apr 25, 2004

Ok, it goes like this.

In my MySQL DB, there are 2 tables.
users and friends

users is basic stuff, and a user_id

friends is as follows
id (key)
user_id (user whose friend this is)
friend_id (user_id of this friend)

Sounds simple, right?

I have a function called get_friends.
It goes like this :

//the degree parameter is nothing (yet!)
function get_friends($user_id, $degree = 1) {
  $qry = "SELECT users.user_name,friends.friend_id FROM users INNER JOIN friends ON friends.friend_id = users.user_id WHERE friends.user_id = $user_id";
$this->db_query($qry);
return $this->results;
}

(if the database stuff seems odd, it's because the functionality is built right into the class)

Here's what I need to do - Get Friends (degree = 1), Friends of Friends (degree = 2), or Friends of Friends of Friends (degree = 3)

Any ideas on how to write this kind of function?
I just want to be able to pass it a degree, and have it return an array of user names and user id's

Thanks so much in advance...
PLEASE HELP!!!

laserlight · Apr 25, 2004

I must be getting rusty, but I found it interesting...
since a normal recursive solution probably wont work as your database handling capability is handicapped to handle only 1 query and result set at a time.

Here's my iterative algorithm:

function: get_friends
argument: user_id (passed by value)
argument: degree (passed by value)
//assume array indices start from 0
set array ret_array = user_id => user_name
set array user_ids = 0 => user_id
set integer start = 0
loop for integer i = degree to i = 1, i = i - 1
	set  integer size = size of user_ids array
	if start >= size
		//no more friends were added in previous iteration
		break out of loop
	endif
	loop for integer j = start to j = size - 1, j = j + 1
		query database for friends of user_ids[j]
		get friends_array for friends of user_ids[j] query result
		loop through friends_array
			if friend's user_id not in user_ids array
				add friend's user_id to user_ids array
				add friend's {user_id, user_name} to ret_array
			endif
		endloop
	endloop
	set start = size
endloop
return ret_array

and my implementation:

function get_friends($user_id, $degree) {
	$ret_array = array($user_id => '');
	$user_ids = array($user_id);

$start = 0;
for ($i = $degree; $i > 0; $i--) {
	$size = count($user_ids);
	if ($start >= $size)
		break;
	for ($j = $start; $j < $size; $j++) {
		$qry = "SELECT `users.user_name`,`friends.friend_id`
			FROM `users`
			INNER JOIN `friends` ON `friends.friend_id` = `users.user_id`
			WHERE `friends.user_id` = '{$user_ids[$j]}'";
		$this->db_query($qry);
		while ($row = $this->db_fetch_array()) {
			$key = $row['user_id'];
			if (!in_array($key, $user_ids)) {
				$user_ids[] = $key;
				$ret_array[$key] = $row['user_name'];
			}
		}
	}
	$start = $size;
}
//note: dummy first element still here
//you may need to remove it instead
//or ignore it in the caller
return $ret_array;
}

silent · Apr 25, 2004

Hehe... that's a very nice looking solution.
I'll have to give this one a try as soon as I get home from work.

PS: What did you mean by this?

since a normal recursive solution probably wont work as your database handling capability is handicapped to handle only 1 query and result set at a time.

MySQL is handicapped? Does it get the good parking spaces?
But seriously, are you referring to a limitation of MySQL?
If so, what database system would make something like this easier?

laserlight · Apr 25, 2004

Nope, it isnt a limitation with mysql.

It's a limitation of your class that provides a wrapper for mysql.

Consider:

$result1 = mysql_query("SELECT * FROM `table1`");
$result2 = mysql_query("SELECT * FROM `table2`");

What's the equivalent if you only have $this->results ?

Basically, if you separate the database wrapper from your class, you'll be able to handle this more cleanly.
In fact, the very idea of using classes is so that each class can encapsulate a given set of related data with its related functions, not be a be-all-end-all solution for saving the world (and some).

silent · Apr 25, 2004

Ahh.. Ok.

I have a question about the code you gave me.
It sort of works...

Here's what happens :
User 'Al' has 2 friends.
Friends are : 'Brian' and 'Friend'

Here's what happens when I print_r the results of
$this->get_friends(1,1);

Array ( [1] => [] => brian )

silent · Apr 25, 2004

I had a little thought (doesn't happen very often!)
How would you write this script if I wasn't using a database wrapper?

I'm not opposed to not using the wrapper.
It's a simple one anyway, only about 20 lines.

I only use it because it gets very tedious dealing with the ins and outs of mysql's functions.

But if it makes this code easier/better to implement without the wrapper, then I say throw the wrapper out!

Thanks a bunch!

laserlight · Apr 25, 2004

hmm... something went wrong.

That means there are 2 elements returned.
The first one is the dummy blank element to get the whole thing going, which is basically the user_id=1 corresponding with a name we didnt put in.

The second one has name "brian", but somewhere along the line the user_id failed to be retrieved.
I would think the script should have failed completely, actually.

The correct results should give 3 elements returned.
You should check the query, does it even return 2 rows?
If it does, then somehow the while loop only iterates once.

silent · Apr 25, 2004


function get_friends($user_id, $degree = 2) { 
    $ret_array = array($user_id => ''); 
    $user_ids = array($user_id); 

$start = 0; 
for ($i = $degree; $i > 0; $i--) { 
    $size = count($user_ids); 
    if ($start >= $size) 
        break; 
    for ($j = $start; $j < $size; $j++) { 
            $qry = "SELECT users.user_id,users.user_name,friends.friend_id 
            FROM users 
            INNER JOIN friends ON friends.friend_id = users.user_id
            WHERE friends.user_id = '{$user_ids[$j]}'"; 
        $this->db_query($qry); 
        foreach($this->results as $row) {
            $key = $row['user_id']; 
            if (!in_array($key, $user_ids)) { 
                $user_ids[] = $key; 
                $ret_array[$key] = $row['user_name']; 
            } 
        } 
    } 
    $start = $size; 
} 
  unset($ret_array[$user_id]);  

  return $ret_array; 
}

There was no user_id in the query!
It works great!
ThankyouThankyouThankyouThankyouThankyouThankyouThankyouThankyouThankyouThankyouThankyouThankyouThankyou!!!!

I have trouble wrapping my brain around things like this..
thank you again!

laserlight · Apr 25, 2004

Nothing much, just a slight change to:

function get_friends($user_id, $degree) {
    $ret_array = array($user_id => '');
    $user_ids = array($user_id);

$start = 0;
for ($i = $degree; $i > 0; $i--) {
    $size = count($user_ids);
    if ($start >= $size)
        break;
    for ($j = $start; $j < $size; $j++) {
        $qry = "SELECT `users.user_name`,`friends.friend_id`
            FROM `users`
            INNER JOIN `friends` ON `friends.friend_id` = `users.user_id`
            WHERE `friends.user_id` = '" . $user_ids[$j] . "'";
        $result = mysql_query($qry);
        while ($row = mysql_fetch_array($result)) {
            $key = $row['user_id'];
            if (!in_array($key, $user_ids)) {
                $user_ids[] = $key;
                $ret_array[$key] = $row['user_name'];
            }
        }
    }
    $start = $size;
}
//note: dummy first element still here
//you may need to remove it instead
//or ignore it in the caller
return $ret_array;
}

I did make an extra change to the query itself, maybe it will be clearer that way.

With a good database wrapper, it would have been easier to implement a recursive solution, methinks.
But since we have an iterative solution, then might as well use it.
In theory, recursion is equivalent to iteration, since one can create one's own stack and work with it using iteration.
But recursion tends to use up more resources.
That said, I find good recursive solutions elegant

laserlight · Apr 25, 2004

There was no user_id in the query!
It works great!

Oh yeah :o

Well, no problem

To be on the safe side, check using more users with more friends, and to higher degrees of separation.

silent · Apr 25, 2004

ONE more question...
It's possible that I might need ONLY the 2nd degree of friends (ie: ONLY friends of friends)

I was thinking of a way to do that.

            foreach($this->results as $row) {
                $key = $row['user_id']; 
                if (!in_array($key, $user_ids) && (($degree - $i) + 1) == $degree) { 
		    $user_ids[] = $key; 
                    $ret_array[$key]['user_name'] = $row['user_name']; 
                    $ret_array[$key]['user_id'] = $row['user_id'];
                    $ret_array[$key]['degree'] = ($degree - $i) + 1; 
                }

When I do it this way, it only shows the 1st degree!
I don't understand why this isn't working.

laserlight · Apr 25, 2004

I would suggest writing a new function for degree-specific listing.

Basically, you do the same thing, except that you only enter into $ret_array on the last iteration of the outmost loop(i.e. $i = 1).

You still must enter into $user_ids for all the iterations, though.

silent · Apr 25, 2004

Ok, that makes sense.

Thank you for all of your help!
I will be sure to mention you in the credits to the site I am making.

PS: Here's the new snippet :

            foreach($this->results as $row) {
                $key = $row['user_id']; 
                if (!in_array($key, $user_ids)) { 
		            $user_ids[] = $key; 
                    if(($degree -$i) + 1 == $degree) {
					$ret_array[$key]['user_name'] = $row['user_name']; 
                    $ret_array[$key]['user_id'] = $row['user_id'];
                    $ret_array[$key]['degree'] = ($degree - $i) + 1; 
					}

laserlight · Apr 25, 2004

oops, I just realised: what I just wrote means the modification is trivial:

The modified code with your user_id correction:

function get_friends($user_id, $degree, $spec_degree = false) {
    $ret_array = array($user_id => '');
    $user_ids = array($user_id);

$start = 0;
for ($i = $degree; $i > 0; $i--) {
    $size = count($user_ids);
    if ($start >= $size)
        break;
    for ($j = $start; $j < $size; $j++) {
        $qry = "SELECT `users.user_id`,`users.user_name`,`friends.friend_id`
            FROM `users`
            INNER JOIN `friends` ON `friends.friend_id` = `users.user_id`
            WHERE `friends.user_id` = '" . $user_ids[$j] . "'";
        $result = mysql_query($qry);
        while ($row = mysql_fetch_array($result)) {
            $key = $row['user_id'];
            if (!in_array($key, $user_ids)) {
                $user_ids[] = $key;
                if (!$spec_degree || $i == 1)
                	$ret_array[$key] = $row['user_name'];
            }
        }
    }
    $start = $size;
}
//note: dummy first element still here
//you may need to remove it instead
//or ignore it in the caller
return $ret_array;
}

laserlight · Apr 25, 2004

I will be sure to mention you in the credits to the site I am making.

hmm... what site are you making?

Oh yes, and the finished function:

function get_friends($user_id, $degree = 1, $spec_degree = false) {
	$ret_array = array($user_id => ''); //to be returned
	$user_ids = array($user_id); //temporary array

$start = 0; //start of loop
for ($i = $degree; $i > 0; $i--) {
	$size = count($user_ids); //number of user_ids added as friends
	if ($start >= $size)
		break; //we're out of range (no more user_ids to add)
	//loop through $user_ids array from $start to current end
	for ($j = $start; $j < $size; $j++) {
		$qry = "SELECT `users.user_id`,`users.user_name`,`friends.friend_id`
			FROM `users`
			INNER JOIN `friends` ON `friends.friend_id` = `users.user_id`
			WHERE `friends.user_id` = '{$user_ids[$j]}'";
		$result = mysql_query($qry);
		//loop through list of friends
		while ($row = mysql_fetch_array($result)) {
			//is this friend already listed?
			if (!in_array($row['user_id'], $user_ids)) {
				//not a duplicate, so we add it
				$user_ids[] = $row['user_id'];
				//do we return only at specified degree?
				if (!$spec_degree || $i == 1)
					$ret_array[$row['user_id']] = $row['user_name'];
			}
		}
	}
	$start = $size; //set loop to start for next iteration
}
//return array excluding dummy element at position 0 used to start looping
return array_slice($ret_array, 1);
}

silent · Apr 25, 2004

hmm... what site are you making?

It's for Cal State University Northridge's (in California) Jewish Community (called Hillel)

And thanks to you, my biggest hurtle is no longer so.
I cannot thank you enough!

It's sort of a simple friendster.com clone.
I plan on making it flexible, and I will probably just GPL it and let anyone use it.

Recursive function help...

Ssilent

laserlight

Ssilent

laserlight

Ssilent

Ssilent

laserlight

Ssilent

laserlight

laserlight

Ssilent

laserlight

Ssilent

laserlight

laserlight

Ssilent