...

View Full Version : A Tree From a Database



smeshy123
06-17-2005, 05:37 AM
I'm developing a website for a newspaper, what I would like to be able to do is for the Archives set up the system so that it takes all the information in the database and makes it look like this:



+ Year
+ Year
- Year
+ Month
+ Month
- Month
Page 1 Link
- Description of Page
Page 2 Link
- Description of Page


That kind of thing. How would that be done? I have no clue where to start. Can anyone point me in the right direction? If you need more details please ask.

Thanks!

Smesh

AaronW
06-17-2005, 01:47 PM
Um, was there supposed to be some kind of hierarchy in your example? Try using the CODE tags to preserve the whitespace.

I'd imagine you meant:



+ Year
+ Year
- Year
+ Month
+ Month
- Month
Page 1 Link
- Description of Page
Page 2 Link
- Description of Page


Am I right? For that, you'd probably be best using an algorithm known as the "Adjacency List Model".

Basically you have one MySQL table called "categories". It looks like:


id | parent | name

Then you'd stuff it with categories and fill in the IDs like so:



1 | 0 | Farm Animals
2 | 1 | Sheep
3 | 1 | Cows
4 | 1 | Birds
5 | 4 | Chickens
6 | 4 | Ducks


So "Farm Animals" has no parent. Sheep, Cows, and Birds use "Farm Animals" as their parent. Chickens and Ducks use "Farm Animals > Birds" as their parent, because Chickens uses 4 as its parent and 4 (Birds) uses 1 (Farm Animals) as its parent. Then you'd simply query the table and loop through the results using PHP to build your tree.

Was that helpful at all? Heh.

smeshy123
06-18-2005, 06:20 AM
I'm sort of getting it. Could you elaborate a little further? Or send me to a good resource on how to do it?

Thanks!

Smesh

AaronW
06-18-2005, 12:18 PM
Here's a class I wrote (see the comments for instructions) to handle such tables: (Copy the code into an editor of some kind so you can read it more clearly... It's sort of butchered here while presented in HTML)



<?php
/*------------------------------------------------------------------------*\
This class is for handling tables that are designed for the adjacency list
model:

id | parent | name
---+--------+--------------
1 | 0 | Farm Animals
2 | 1 | Sheep
3 | 1 | Cows
4 | 1 | Birds
5 | 4 | Chickens
6 | 4 | Ducks

The id, parent, and name field names in this example table are 'id',
'parent', and 'name'.
\*------------------------------------------------------------------------*/
class AdjacencyList
{
var $raw_nodes = array ();
var $nodes = array ();
var $separator = ' > ';

/*----------------------------------------------------------------------*\
Function: object AdjacencyList ( resource result, string id_field, string parent_field, string name_field )
Description: Given a MySQL result, this will build an array of $nodes
and $raw_nodes which are keyed and sorted by their paths.
The three $*_field arguments are to be filled out with the
names of the fields in the result.

Example:
// Select as many fields as you want, but you need the id, parent, and name fields
$result = mysql_query ('SELECT id, parent_id, name, date, creator FROM categories');

// Build the tree, and give it our 'categories' table's id, parent, and name field names
$tree = new AdjacencyList ($result, 'id', 'parent_id', 'name');

// Output HTML List of the tree
echo $tree->to_html ();
\*----------------------------------------------------------------------*/
function AdjacencyList ($result, $id_field, $parent_field, $name_field)
{
while ($category = mysql_fetch_object ($result))
$this->raw_nodes[$category->{$id_field}] = $category;

// Traverse the raw nodes and build the associative array
foreach ($this->raw_nodes as $key => $node)
{
$path = $node->{$name_field};
$child_id = $node->{$id_field};

// Build verbose path to the category
while ($node->{$parent_field})
{
$parent = $this->raw_nodes[$node->{$parent_field}];
$path = $parent->{$name_field}.$this->separator.$path;
$node = $parent;
}

// Add node as a child of its direct parent
$bricks = explode ($this->separator, $path);
array_pop ($bricks);
if (count ($bricks))
{
$parent_obj =& $this->nodes[implode ($this->separator, $bricks)];
$parent_obj->children[$this->raw_nodes[$child_id]->{$name_field}] =& $this->raw_nodes[$child_id];
}

// Cross-reference the two node arrays. I think using references saves memory...
$this->nodes[$path] =& $this->raw_nodes[$key];
$this->nodes[$path]->path = $path;
}

// Sort the tree and its branches alphabetically
ksort ($this->nodes);
}

/*----------------------------------------------------------------------*\
Function: string to_html ( [string current [, string css_class [, string css_id ]]] )
Description: Traverse the nodes and build the HTML for a <ul>, with a
nested <ul> for each branch. CSS #id and the ID/Path of
the currently-selected category can be customized.
$current is the $path of the currently-selected node. That
is, for example: 'Animals > Cow'. The <li> containing this
branch will be giving a CSS class of 'current' for unique
styling.
\*----------------------------------------------------------------------*/
function to_html ($current = '', $css_id = '', $css_class = '')
{
// Monitor depth, and open/close a new list when it changes between nodes
$last_depth = 0;

if ($css_id != '')
{
$css_id = ' id="'.$css_id.'"';
}
if ($css_class != '')
{
$css_class = ' class="'.$css_class.'"';
}

$html = '<ul'.$css_id.$css_class.'>';
foreach ($this->nodes as $node)
{
// Current category?
$class = '';
if ($node->path == $current)
$class = 'current';

$depth = substr_count ($node->path, $this->separator);

if (!empty ($node->children))
$html .= '<li class="parent'.$class.'">'.$node->name.'<ul'.$css_class.'>';
else
{
if ($depth < $last_depth) $html .= '</ul></li>';
$html .= '<li'. (!empty ($class) ? ' class="'.trim ($class).'"' : '').'>'.$node->name.'</li>';
}

$last_depth = $depth;
}
if ($last_depth != 0) $html .= '</ul></li>';
$html .= "</ul>";

return $html;
}
}
?>

smeshy123
06-18-2005, 05:34 PM
Thanks! That was a great help!

Smesh



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum