cascading (potentially) infinite lists

[jasonmills58]

Hi folks,

Ok, so not infinte levels, but I'm playing around with a little friends list sort of thing which cascades out and shows who knows who. I'm having trouble coming up with a script that will continuously expand, based on showing everyone I know, and everyone each one of them knows, without having some finite limit. I have this script:

<?
$data = mysql_query( "SELECT * FROM friends WHERE topFriend='Jason' ORDER BY name" );
while ( $a_row = mysql_fetch_array( $data ) ) {
?>
	<font style="bold" size="5"><? print $a_row['name']; ?></font>
	<? 
	if ( ! empty( $a_row['link'] ) ) { 
	?>
		<a href="<? print $a_row['link']; ?>">
		<font style="bold" size="5">
			<? print $a_row['link']; ?>
		</font>
		<a/>
		<br />
	<?
	}
}
?>

And I can easily expand this to manually have 5, 6, 7, or however many finite levels, but I want it to be unlimited. Am I making sense?

Thanks for any help.
Jason

[Shrike]

To do what you want to do, you'll need to use a recursive function. I'm not quite sure on the layout you want, but presumably you need to select your list of friends from the database, and then for each of those, select their list of friends and display those indented from the first list.

One problem I can see is that if someone on one of your friends' lists has you as a friend, you could run into infinite recursion. But ignoring that for the moment 😉

$indent = 0;
function getFriendList($id)
{
  global $indent;
  $res = mysql_query("SELECT stuff FROM table WHERE id = '$id'");
  while($friends = mysql_fetch_assoc($res))
  {
    // Do some display layup using $indent
    ++$indent; // Move one level deeper
    getFriendList($friends[$id]); // Recurse
  }
}

Each time you recurse, the current function contents are added to a stack and returned to once the new function ends. If you have a very large amount of data to process, you might run into a stack overflow. I'm not sure on PHP's limits in this regard though.

[jasonmills58]

Thank you for that Shrike. I have enforced a "top down" structure - its actually going to be for a game where people have a commander and officers, but I want it to flow down through the officers' officers and it looks like this should do it.

Stack overflow also shouldn't be a problem. I don't ever expect to have huge numbers of people here.

So, looking through the code again - will this come back out from the indent, when done with the first friend? For instance, I have listed below me, Jackie, Dan, and Tom. And they have friends, like so:

Jason
  Jackie
    friend1
    friend2
  Dan
    friend1
    friend2
    friend3
  Tom
    friend1

Recursive functions are new to me, be gentle... 😃

[Shrike]

Yes that's right. I forgot to add one important thing though - you will need to decrease the indent after the recursion, so the code looks like this:

$indent = 0; 
function getFriendList($id) 
{ 
  global $indent; 
  $res = mysql_query("SELECT stuff FROM table WHERE id = '$id'"); 
  while($friends = mysql_fetch_assoc($res)) 
  { 
    // Do some display layup using $indent 
    ++$indent; // Move one level deeper 
    getFriendList($friends[$id]); // Recurse 
    --$indent; // Go back up
  } 
}

Also, the reason for using a global variable is so it is outside of the whole recursion process, static if you like.

Bad point: currently every friend will get displayed at the top level, though maybe without any sub-levels. So you might need to find a way around that 😉

This problem is a common one, which crops up alot on the board particularly in relation to dynamic heirarchical menus. You might want to do some research into the Tree model, which while fairly complex is a good solution to nested data. There is also a PEAR package for this 🙂

[jasonmills58]

Oh, I also have the benefit of a constant start - it always starts with me. How would I incorporate this call where the starting 'commander' will always be me? I also need to include some info next to each name, which is part of their DB entry... ah, I'm not seeing where this data is outputted to. Would I just use the print function inside the getOfficerList function?

so far...

<?
$indent = 0;
function getOfficerList($commander)
{
	global $indent;
	$res = mysql_query("SELECT * FROM officers WHERE commander = '$commander'");
	while($officers = mysql_fetch_assoc($res))
	{
	// Do some display layup using $indent
	++$indent; // Move one level deeper
	getOfficerList($officers[$commander]); // Recurse
	}
}

[Shrike]

After thinking for a bit, I realised that your solution would only allow 1 person to have 1 friend. To allow multiple friends you should use a lookup table in addition to the people table. Here's a bit of code I knocked together, you can play with and see how it works 🙂

# MySQL dump
CREATE TABLE `lookup` (
  `id` int(11) default NULL,
  `id_friend` int(11) default NULL
) TYPE=MyISAM;
INSERT INTO lookup VALUES("1","2");
INSERT INTO lookup VALUES("1","3");
INSERT INTO lookup VALUES("2","5");
INSERT INTO lookup VALUES("2","4");
INSERT INTO lookup VALUES("3","6");

CREATE TABLE `people` (
  `id` int(11) unsigned NOT NULL auto_increment,
  `name` varchar(25) default NULL,
  `rank` varchar(25) default NULL,
  PRIMARY KEY  (`id`)
) TYPE=MyISAM;
INSERT INTO people VALUES("1","Jim","Commander");
INSERT INTO people VALUES("2","John","Captain");
INSERT INTO people VALUES("3","Jane","Captain");
INSERT INTO people VALUES("4","Joe","Grunt");
INSERT INTO people VALUES("5","Jack","Grunt");
INSERT INTO people VALUES("6","Jackie","Grunt");

$indent = 0;  

function getFriendList($id)  

{
  global $indent;  

  $res = mysql_query("
  	SELECT t1.id, t1.name, t1.rank FROM people AS t1
  	INNER JOIN lookup as t2
  	ON t2.id = '$id'
  	WHERE t2.id_friend = t1.id
  	ORDER BY t1.id
  ");
  while($friends = mysql_fetch_assoc($res))  

  {
    // Do some display layup using $indent
    echo str_repeat("&nbsp;", $indent).$friends['rank']." ".$friends['name']."<br>";
    ++$indent; // Move one level deeper 
    getFriendList($friends['id']); // Recurse 
    --$indent; // Go back up 
  }  

}
echo "General Jim<br>"; // Gotta do this as we're not looking up the highest member's details
++$indent;
getFriendList(1);

Hope this is the kinda thing you were looking for. Now gotta run, late for work 😃

[PHPMagician]

Could you possibly post the schema of the DB. I don't really see how friends are references together. I mean, I can see that topFriend is the best friend or whatever, but how do you have relationships (in a database sense, not in a friendship sense) between secondary friends. If you know what I mean.

[Shrike]

I did post the schema. I've added a little explaination:

# MySQL dump

# This table is for forming relationships between rows
# The id field refers to one row in people, and the id_friend field refers to the id of other rows in people
# We use this with an INNER JOIN to retrieve a list of rows related to a given id
CREATE TABLE `lookup` (
  `id` int(11) default NULL,
  `id_friend` int(11) default NULL
) TYPE=MyISAM;
# Some sample data
INSERT INTO lookup VALUES("1","2");
INSERT INTO lookup VALUES("1","3");
INSERT INTO lookup VALUES("2","5");
INSERT INTO lookup VALUES("2","4");
INSERT INTO lookup VALUES("3","6");

# This table specifies the details of each person
# The id field is related in the lookup table, the other fields are just for information
CREATE TABLE `people` (
  `id` int(11) unsigned NOT NULL auto_increment,
  `name` varchar(25) default NULL,
  `rank` varchar(25) default NULL,
  PRIMARY KEY  (`id`)
) TYPE=MyISAM;
# Some sample data
INSERT INTO people VALUES("1","Jim","Commander");
INSERT INTO people VALUES("2","John","Captain");
INSERT INTO people VALUES("3","Jane","Captain");
INSERT INTO people VALUES("4","Joe","Grunt");
INSERT INTO people VALUES("5","Jack","Grunt");
INSERT INTO people VALUES("6","Jackie","Grunt");

// Set the indent counter
$indent = 0;
// the recursive function
function getFriendList($id)  

{
  // Get global variable to local scope
  global $indent;
  // Query the database, based on the $id parameter passed to the function
  $res = mysql_query("
      SELECT t1.id, t1.name, t1.rank FROM people AS t1
      INNER JOIN lookup as t2
      ON t2.id = '$id'
      WHERE t2.id_friend = t1.id
      ORDER BY t1.id
  ");
  // while() loop to loop through the returned recordset
  while($friends = mysql_fetch_assoc($res))  

  {
    // Do some display layup using $indent
    echo str_repeat("&nbsp;&nbsp;", $indent).$friends['rank']." ".$friends['name']."<br>";
    // Move one level deeper
    ++$indent; 
    // Recurse
    getFriendList($friends['id']);
    // Go back up
    --$indent;
  }  

}
// Gotta do this as we're not looking up the highest member's details
echo "General Jim<br>";
// Move one level deeper
++$indent;
// Start function
getFriendList(1);

Hope this explains things more clearly.

[PHPMagician]

Originally posted by Shrike
I did post the schema.

Sorry, I should have been more specific. I wanted jasonmills58 to post his schema, if he already had one. Obviously though you have a solution so I suppose the problem is resolved.

[Shrike]

Ack sorry 🙂

[jasonmills58]

Sure. Basically, I have the 'officers' table with

officerid //auto-increment, smallint
officer //varchar for names
commander // varchar for names
link // varchar for a hyper-link

Also, the top of list will always be me, so at least the start is easy.

Thats pretty much it. Thanks for all the input, I'll go through it later today...

Cheers!