Displaying a hierachy with php

meghatronic · 25 Mar 2008 at 16:03

I have a mysql table that contains parent|child. Just two columns and 800 rows.

I'd like to extrapolate a familial relation from this list. And wrote something in PHP to do this, however it is VERY inefficient. There can be up to 8 or 9 levels on the hierachy in places, in others just 2. I was writing it in a case-by-case way... but proved too long and inefficient!

There must be an easy way to iterate up and down the list to use:

food|cheese
drink|wine
drink|beer
drink|soda
wine|red
wine|white
beer|lager
beer|bitter
beer|ale

to produce, for example if I searched for lager:

drink

beer

lager

bitter

ale

soda

wine

red

white

note food and cheese wasn't called.

Sic · 26 Mar 2008 at 07:10

could you give me an example of how this data is actually returned? I'm having a hard time picturing it based on your explanation. Could you var_dump() the array returned from a query to this table and I'll take a look for you? It'll need a recursive function, but I'll have a better idea of which one with some data

meghatronic · 26 Mar 2008 at 10:48

Sic said:
could you give me an example of how this data is actually returned? I'm having a hard time picturing it based on your explanation. Could you var_dump() the array returned from a query to this table and I'll take a look for you? It'll need a recursive function, but I'll have a better idea of which one with some data

The data is just stored in the database at the moment as parent/child list.

I was recurisvely searching upwards. For example:

1) User searches for ale.
2) Db queries for parents to ale.
3) Does parents have parents? and so on up the tree.
4) Do each of these parents have parents and children? and so on up and down the tree.

I'm sorry I'm not expalining it well

Sic · 26 Mar 2008 at 11:10

yeah, what I mean is run a query to gain an array/object out of the database, run that array/object through the var_dump() function and post the result.

LazyManc · 26 Mar 2008 at 12:08

Haven't got the time to write a search algorithm atm but if you haven't got an index on each column then it may speed things up a bit by adding them.

PS - it's an interesting problem though, i'd probably approach it as follows:

A findParent() function that takes a search param, queries the db for a parent and recursively calls itself until it finds the root node, and then returns each node it found on the way.

A findChildren() function that does the reverse of findParent() until it finds the leaf nodes.

Bolt the results from the two together and you should have the full hierachy.

meghatronic · 26 Mar 2008 at 15:23

LazyManc said:
Haven't got the time to write a search algorithm atm but if you haven't got an index on each column then it may speed things up a bit by adding them.

PS - it's an interesting problem though, i'd probably approach it as follows:

A findParent() function that takes a search param, queries the db for a parent and recursively calls itself until it finds the root node, and then returns each node it found on the way.

A findChildren() function that does the reverse of findParent() until it finds the leaf nodes.

Bolt the results from the two together and you should have the full hierachy.

This is what I started doing this morning, only it doesn't work!

The findparent bit:

Code:

//process hierarchy
function get_parent($child)
  {
	
	$query = "SELECT `parent` FROM `hierarchy` WHERE `child` = '" . $child . "'";
	$result = mysql_query($query) or die('Error, query failed');
	$num_results =  mysql_num_rows($result);

	if ($num_results == 1) {
		while ($rows = mysql_fetch_array($result)) {
			$parent = trim($rows['parent']);
			
			if ($parent != null){
				get_parent($parent);
			}
		}
	}
	return $parent;
	}

echo get_parent($gc);

It calls only the $gc parent, not the overall top parent. If I echo out $parent on the if not null line, it does echo them out.... though.

LazyManc · 26 Mar 2008 at 15:49

This should work...

PHP:

/*
 * Recursively finds parent nodes
 * 
 * return array $tree
 */
function findParent($node, $prevNodes = NULL) {
    $query = "SELECT * FROM parent_child WHERE child = '$node'";
    
    // some error checking
    $result = mysql_query($query) or die('SQL Error: ' . mysql_error());
    
    // if there are no results, $node has no parent and is a root node
    if(mysql_num_rows($result) == 0) {
        return array($node => $prevNodes);
    } else {// we need to search again using the parent as the search node
        $row = mysql_fetch_assoc($result);
        return findParent($row['parent'], array($node => $prevNodes));
    }
}

$tree = findParent('lager');
print_r($tree);

[edit] - sorry, I somehow missed the post where you said you were already recursively searching.
The trick is to build the tree as you go, otherwise there's no way to know what level each node is at.

The above function will only work for direct parents, if you want sibling nodes and their children you'll have to call your findChildren() function for each call to findParent() and add them to the tree.

meghatronic · 26 Mar 2008 at 20:18

Thank to LazyManc's help, I've now got the following:

PHP:

function findParent($child) {
    $query = "SELECT * FROM hierarchy WHERE child = '$child'";
    $result = mysql_query($query) or die('Error, query failed: ' . mysql_error());
    
    if(mysql_num_rows($result) == 0) {
        return $child;
    } else {
        $row = mysql_fetch_assoc($result);
        return findParent($row['parent']);
    }
}


function findChildren($parent) {
$children[$parent] = array();
    $query = "SELECT child FROM hierarchy WHERE parent = '$parent'";
    $result = mysql_query($query) or die('Error, query failed: ' . mysql_error());
		while ($row = mysql_fetch_array($result)) {
		array_push($children[$parent], $row['child']);		
		}		
	print_r($children);
}

$top_parent = findParent($gc);
findChildren($top_parent);

Naturally it doesn't return children's children and so on as I haven't figured out how to do that yet!

EDIT: Got the below to work (although it isn't recursive!) to check all the information is there. It only goes a few levels deep though as it isn't recursive. Any pointers?

PHP:

foreach ($arr as $key => $value) {
   echo $key . "<br>";

   foreach ($value as $split) {
   $new = findChildren($split);
   foreach ($new as $keya => $valuea) {
		echo "&nbsp;&nbsp;&nbsp;" . $keya . "<br>";
   foreach ($valuea as $bits) {
		echo "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;" . $bits . "<br>";
			$newa = findChildren($bits);
				foreach ($newa as $valueb) {
									foreach ($valueb as $valuec) {
					echo "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;" . $valuec . "<br>";
					$newb = findChildren($valuec);
					foreach ($newb as $valued) {
									foreach ($valued as $valuee) {
					echo "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;" . $valuee . "<br>";
					}
					}
					}
					}
					
			}
		}	
   }
}

LazyManc · 26 Mar 2008 at 22:20

This is my bash at a findChildren() function... as before it returns a nested array.

PHP:

/*
 * Recursively find children nodes
 *
 * return array $tree    
 */
function findChildren($node) {
    $query = "SELECT * FROM parent_child WHERE parent = '$node'";
    $result = mysql_query($query) or die('SQL Error: ' . mysql_error());
    
    // if there are no results, $node has no children and is a leaf node
    if(mysql_num_rows($result) == 0) {
        return NULL;
    } else { // for each child node, check for more children
        while($row = mysql_fetch_assoc($result)) {            
            $children[$row['child']] = findChildren($row['child']);
        }
        
        return $children;
    }
}

Calling the two functions separately like so:

PHP:

$parent = findParent('beer');
echo "<pre>";
print_r($parent);  
echo "</pre>";

$children = findChildren('beer');
echo "<pre>";
print_r($children);  
echo "</pre>";

results in something like:

Code:

Array
(
    [drink] => Array
        (
            [beer] => 
        )

)
Array
(
    [lager] => Array
        (
            [stella] => 
            [harp] => 
        )

    [bitter] => Array
        (
            [boddingtons] => 
            [tetley] => 
        )

    [ale] => Array
        (
            [bishops finger] => 
        )

)

How hard it would be to piece the two together I have no idea!

meghatronic · 26 Mar 2008 at 22:45

LazyManc said:
How hard it would be to piece the two together I have no idea!

Cheers dude, I'll try that later.

I'm pleased to say I've finished it... half of it in an intelligent recurvise fashion. Half of it in a very naughty way. As I know how many levels there are, I've merely nested foreach loops

I must fix this to be honest!

EDIT - What I mean is:

PHP:

$top_parent = findParent($gc);

$children = findChildren($top_parent);

echo boldit($top_parent, $gc) . "<br>";
foreach ($children as $key => $value) {
   echo "&nbsp;&nbsp;&nbsp;" . boldit($key, $gc) . "<br>";
      if ($value!=null){
		foreach ($value as $keya => $valuea) {
			echo "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;" . boldit($keya, $gc) . "<br>";
			if ($valuea!=null){
			foreach ($valuea as $keyb => $valueb) {
			echo "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;" . boldit($keyb, $gc) . "<br>";
			if ($valueb!=null){
			foreach ($valueb as $keyc => $valuec) {
			
			echo "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;" . boldit($keyc, $gc) . "<br>";
		}
		}
		}
		}
		}
		}
		}

(please forgive indentation, my tab key doesn't work)

meghatronic · 28 Mar 2008 at 20:01

Any ideas how to make the above recursive?

It's pretty lazy/bad of me to do it like that... some pointers would be great!