A community in which webmasters can ask for help with topics such as PHP coding , MySQL , IT jobs, web design, IT security.
Current location:homephp forumphp talk in 2009 yearAdjacency tree from single table - page 1
User InfoPosts
Adjacency tree from single table#1
I(ve read a lot of people discussing nested lists, but I was wondering how to iterate through an adjacancy list/tree in PHP.

I have a table with: id, title, parent_id

And I(ve selected all records out into an array called $pages.

Then using this php:

function makeList($pages, $used) {
if (count($pages)) {
echo "<ul>";
foreach ($pages as $page) {
echo "<li>".$page[(pag_title(];
$par_id = $page[(pag_id(];
$subsql("SELECT * FROM pages WHERE pag_parent = ".$par_id."");

// running the new sql through an abstraction layer
$childpages = $dbch->fetchAll();
makeList($childpages, $used, $lastused);
echo "</li>";
echo "</ul>";

This sort of works but I end up with any sub menu being repeated e.g.


I(ve tried adding the current id into an array that gets passed through the function, and then using in_array to check if it(s there, but I have had no joy doing that.

Any help would be much appreciated.

I need to parse the whole tree so choosing parent as 0 isn(t an option

posted date: 2009-04-14 07:33:00

Re: Adjacency tree from single table#2
I had made out the solution of this problem. click to view my topic...

hope that hepls.

posted date: 2009-04-14 07:33:01

Re: Adjacency tree from single table#3
The simplest fix would just be, when you are doing the initial select to set $pages (which you don(t show), add a WHERE clause like:WHERE pag_parent = 0(or IS NULL, depending how you(re storing "top level" pages).That way you won(t select all the children initially.

posted date: 2009-04-14 07:39:00

Re: Adjacency tree from single table#4
Where is $page coming from? You might have an sql injection vulnerability in your code if you(re not escaping it or using a prepared statement.Also the SELECT statement inside a for loop jumps out as a bad practice. If the table is not that big, then select the contents of the entire table and then iterate through the result set in PHP to build the tree data structure. This could take up to n*(n-1)/2 iterations in the pathological case of your tree being a linked list. Stop when all nodes have been added to the tree, or the number of remaining nodes remains the same from one iteration to the next - this means the remaining nodes are not children of your root node.Alternatively, if your database supports recursive SQL queries, you can use that, and it will only select the nodes that are children of your parent node. You will still have to build the tree object yourself in PHP. The form of the query would be something like:WITH temptable(id, title, parent_id) AS ( SELECT id, title, parent_id FROM pages WHERE id = ? UNION ALL SELECT a.id, a.title, a.parent_id FROM pages a, temptable t WHERE t.parent_id = a.id) SELECT * FROM temptableSubstitute the (?( on the second line with the starting page ID.

posted date: 2009-04-14 08:18:00

Re: Adjacency tree from single table#5
Since it already does the SQL, you dont have to do it outside before the first function call.function makeList($par_id = 0) { //your sql code here $subsql("SELECT * FROM pages WHERE pag_parent = $par_id"); $pages = $dbch->fetchAll(); if (count($pages)) { echo (<ul>(; foreach ($pages as $page) { echo (<li>(, $page[(pag_title(]; makeList($page[(pag_id(]); echo (</li>(; } echo (</ul>(; }}For storing it more tree like you might want to look at this site: Storing Hierarchical Data in a Database.

posted date: 2009-04-14 09:32:00

Re: Adjacency tree from single table#6
$page comes from the $pages array, which itself comes from the sql (the sql selection is done in a seperate class, and everything is escaped to avoid sql injection) It's the php that I'm interested in, not the SQL, I'm fine with that thanks

posted date: 2009-04-15 00:10:00

Re: Adjacency tree from single table#7
perfect thank you

posted date: 2009-04-15 00:29:00

Re: Adjacency tree from single table#8
If you create an array of pages grouped by parent id it is quite easy to recursively build the list. This will only require one database query.<?php //example data $items = array( array((id(=>1, (title(=>(Home(, (parent_id(=>0), array((id(=>2, (title(=>(News(, (parent_id(=>1), array((id(=>3, (title(=>(Sub News(, (parent_id(=>2), array((id(=>4, (title(=>(Articles(, (parent_id(=>0), array((id(=>5, (title(=>(Article(, (parent_id(=>4), array((id(=>6, (title(=>(Article2(, (parent_id(=>4) ); //create new list grouped by parent id $itemsByParent = array(); foreach ($items as $item) { if (!isset($itemsByParent[$item[(parent_id(]])) { $itemsByParent[$item[(parent_id(]] = array(); } $itemsByParent[$item[(parent_id(]][] = $item; } //print list recursively function printList($items, $parentId = 0) { echo (<ul>(; foreach ($items[$parentId] as $item) { echo (<li>(; echo $item[(title(]; $curId = $item[(id(]; //if there are children if (!empty($items[$curId])) { makeList($items, $curId); } echo (</li>(; } echo (</ul>(; }printList($itemsByParent);

posted date: 2009-04-16 07:06:00

Re: Adjacency tree from single table#9
When that table gets large, recursion can get unwieldy. I wrote an blog post about a recursion-less method: http://www.alandelevie.com/2008/07/12/recursion-less-storage-of-hierarchical-data-in-a-relational-database/

posted date: 2009-04-16 07:58:00

Re: Adjacency tree from single table#10
Will require too many queries.

posted date: 2012-02-14 09:41:00

Re: Adjacency tree from single table#11
@SamDark Yes, I personally would store the data more hierarchical.

posted date: 2012-03-23 02:20:00

Re: Adjacency tree from single table#12
Finding top parent, all parents, and all children of a node (enhancements for Tom Haigh(s answer):<?php //sample data (can be pulled from mysql) $items = array( array((id(=>1, (title(=>(Home(, (parent_id(=>0), array((id(=>2, (title(=>(News(, (parent_id(=>1), array((id(=>3, (title(=>(Sub News(, (parent_id(=>2), array((id(=>4, (title(=>(Articles(, (parent_id(=>0), array((id(=>5, (title(=>(Article(, (parent_id(=>4), array((id(=>6, (title(=>(Article2(, (parent_id(=>4) ); //create new list grouped by parent id $itemsByParent = array(); foreach ($items as $item) { if (!isset($itemsByParent[$item[(parent_id(]])) { $itemsByParent[$item[(parent_id(]] = array(); } $itemsByParent[$item[(parent_id(]][] = $item; } //print list recursively function printList($items, $parentId = 0) { echo (<ul>(; foreach ($items[$parentId] as $item) { echo (<li>(; echo $item[(title(]; $curId = $item[(id(]; //if there are children if (!empty($items[$curId])) { printList($items, $curId); } echo (</li>(; } echo (</ul>(; }printList($itemsByParent);/***************Extra Functionality 1****************/function findTopParent($id,$ibp){ foreach($ibp as $parentID=>$children){ foreach($children as $child){ if($child[(id(]==$id){ if($child[(parent_id(]!=0){ //echo $child[(parent_id(]; return findTopParent($child[(parent_id(],$ibp); }else{ return $child[(title(];} } }}}$itemID=7; $TopParent= findTopParent($itemID,$itemsByParent);/***************Extra Functionality 2****************/function getAllParents($id,$ibp){ //full pathforeach($ibp as $parentID=>$nodes){ foreach($nodes as $node){ if($node[(id(]==$id){ if($node[(parent_id(]!=0){ $a=getAllParents($node[(parent_id(],$ibp); array_push($a,$node[(parent_id(]); return $a; }else{ return array(); } } }}}$FullPath= getAllParents(3,$itemsByParent);print_r($FullPath);/*Array([0] => 1[1] => 2)*//***************Extra Functionality 3****************/ //this function gets all offspring(subnodes); children, grand children, etc... function getAllDescendancy($id,$ibp){ if(array_key_exists($id,$ibp)){ $kids=array(); foreach($ibp[$id] as $child){ array_push($kids,$child[(id(]); if(array_key_exists($child[(id(],$ibp))$kids=array_merge($kids,getAllDescendancy($child[(id(],$ibp)); } return $kids; }else{ return array();//supplied $id has no kids } }print_r(getAllDescendancy(1,$itemsByParent));/*Array([0] => 2[1] => 3)*/print_r(getAllDescendancy(4,$itemsByParent));/*Array([0] => 5[1] => 6)*/print_r(getAllDescendancy(0,$itemsByParent));/*Array([0] => 1[1] => 2[2] => 3[3] => 4[4] => 5[5] => 6)*/?>

posted date: 2014-01-22 12:20:00

select page: « 1 »
Copyright ©2008-2017 www.momige.com, all rights reserved.