Storing a Hierarchy in an Array

Hello all,

Okay, I am having some troubles. What I am doing here is dealing with
an employee hierarchy that is stored in an array. It looks like this:

$employees = array( "user_id" => array( "name", "title",
"reports to user id", "start date in the format: mm/dd/yyyy" )
);

How can I display this hierarchy in simple nested <li> tags in the most
efficient way possible? I realize that the way this is setup, the
hierarchy is essentially a tree. But I am at a loss as to how to pull
this data out, sort it, and display it wit nested <li> tags. I am
thinking that this is more of a computer science problem....

What I mean by displayed as a hierarchy, is that the nested <li> tags
will indent themselves to look like that. Like this:

- CEO
-- Manager
--- Manager's secretary
--- Minion
-- Manager


That sort of thing. I am just lost as to how I can analyze the
structure of the array and turn it in to output like that.

Any help is greatly appreciated.

vcardillo@gmail.com wrote:
[snip]
> How can I display this hierarchy in simple nested <li> tags in the most
> efficient way possible?
[snip]

<?php
echo "<ul>";
foreach($employees as $key => $value) {
echo "<li>" . $key . "</li>";
echo "<ul>";
foreach($value as $value2) {
echo "<li>" . $value2 . "</li>";
}
echo "</ul>";
}
echo "</ul>";
?>

Would look like this:

user_id
name
title
reports to user id
start date in the format: mm/dd/yyyy
another user_id
another name
another title
another reports to user id
another start date in the format: mm/dd/yyyy

....and so on.

Zilla

> $employees = array( "user_id" => array( "name", "title",
> "reports to user id", "start date in the format: mm/dd/yyyy" )
> );
> How can I display this hierarchy in simple nested <li> tags in the most
> efficient way possible? I realize that the way this is setup, the
> hierarchy is essentially a tree. But I am at a loss as to how to pull
> this data out, sort it, and display it wit nested <li> tags. I am
> thinking that this is more of a computer science problem....
>
> What I mean by displayed as a hierarchy, is that the nested <li> tags
> will indent themselves to look like that. Like this:
>
> - CEO
> -- Manager
> --- Manager's secretary
> --- Minion
> -- Manager
>
>
> That sort of thing. I am just lost as to how I can analyze the
> structure of the array and turn it in to output like that.

What I see is that the data is not really designed so well in the array
in the first place. You may try and organize it better for what you are
doing. What I mean by this, is that the data is organized is such a
form that all the CEO's are in one part of the array and the mangagers
are under them etc etc.

The next thing is you should be using a recursive function.

Mike

> Would look like this:
>
> user_id
> name
> title
> reports to user id
> start date in the format: mm/dd/yyyy
> another user_id
> another name
> another title
> another reports to user id
> another start date in the format: mm/dd/yyyy

Hmmm maybe I missed the point on my reply lol!

Mike

No... you're right. Let's say we have this stored in the array,
conceptually:

A reports to B.
B reports to C.
D Reports to C.
E Reports to C.
C Reports to Z
G Reports to Z.

The data has to be formatted like this:

CEO Z
- Person C
-- Person B
--- Person A
-- Person D
-- Person E
- Person G

Each dash (-) should be understood as a tab, and a different bulleted
symbol. This is essentially what I mean. The data can't just be
outputted linearly. The LI tags have to be nested, so as to create the
visual hierarchy.... this is why I am finding it so difficult. The
data structure doesn't really allow for this.

vcardillo@gmail.com wrote:
> No... you're right. Let's say we have this stored in the array,
> conceptually:
>
> A reports to B.
> B reports to C.
> D Reports to C.
> E Reports to C.
> C Reports to Z
> G Reports to Z.
>
> The data has to be formatted like this:
>
> CEO Z
> - Person C
> -- Person B
> --- Person A
> -- Person D
> -- Person E
> - Person G

Sounds like a tree data structure to me. Searching for array
implementation of tree and traversing algorithms might help.

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com Blog: http://rajeshanbiah.blogspot.com/

vcardillo@gmail.com wrote:
> A reports to B.
> B reports to C.
> D Reports to C.
> E Reports to C.
> C Reports to Z
> G Reports to Z.

Oh like that.... then my example doesn't work.... i will think about it
and maybe give a reply later... have to work now...

Zilla

On 15 May 2005 01:20:21 -0700, "R. Rajesh Jeba Anbiah"
<ng4rrjanbiah@rediffmail.com> wrote:

>vcardillo@gmail.com wrote:
> Sounds like a tree data structure to me. Searching for array
>implementation of tree and traversing algorithms might help.

I agree that you are probably looking at a tree structure rather than
an array. Personally I would also use classes to encapsulate the
employees (each employee is effectively a node in the tree) i.e:

class cEmployee {
var $m_userId;
var $m_name;
var $m_title;
var $m_startDate;
var $m_subordinates = array();
function cEmployee($userId,$name,$title,$startDate)
{
$this->m_userId = $userId;
$this->m_name = $name;
$this->m_title = $title;
$this->m_startDate = $startDate;
}
function addSubordinate($item)
{
$this->m_subordinates[] = $item;
}
};

To traverse the tree you would need a function along these lines:

function traverse($h)
{
echo "<ul><li>";
echo $h->m_title;
while (list($key, $val) = each($h->m_subordinates))
{
traverse($val);
}
echo "</li></ul>\n";
};

This is not perfect as even employees who have no subordinates are
still an unordered list themselves i.e:

<ul><li>CEO<ul><li>Manager<ul><li>Managers Secretary</li></ul>
<ul><li>Minion</li></ul>
</li></ul>
<ul><li>Manager</li></ul>
</li></ul>

Then there is also the task of populating the tree to begin with. I
will leave that to you. To get the printout above I used the following
code:

$employeelist = new cEmployee('','','CEO','');
$employeelist->addSubordinate(new cEmployee('','','Manager',''));
$employeelist->m_subordinates[0]->addSubordinate(new
cEmployee('','','Managers Secretary',''));
$employeelist->m_subordinates[0]->addSubordinate(new
cEmployee('','','Minion',''));
$employeelist->addSubordinate(new cEmployee('','','Manager',''));
traverse($employeelist);

Have fun. :-)

> How can I display this hierarchy in simple nested <li> tags in the most
> efficient way possible?

Now I have had the time to look at your problem. Here is what I came up
with. Remember that the CEO(s) should report to themselves or else it
wont work (look at id 1 and 2 which are CEOs).

I used this array to test with:

$employees = array(1 => array("name1", "title1", 1, "date1"),
2 => array("name2", "title2", 2, "date2"),
33 => array("name3", "title3", 15, "date3"),
15 => array("name4", "title4", 10, "date4"),
10 => array("name5", "title5", 1, "date5"),
37 => array("name6", "title6", 15, "date6"),
40 => array("name7", "title7", 33, "date7"),
45 => array("name8", "title8", 10, "date8"),
50 => array("name9", "title9", 37, "date9"),
4 => array("name10", "title10", 2, "date10"),
7 => array("name11", "title11", 23, "date11"),
456 => array("name12", "title12", 50, "date12"),
89 => array("name13", "title13", 4, "date13"),
23 => array("name14", "title14", 25, "date14"),
57 => array("name15", "title15", 45, "date15"),
25 => array("name16", "title16", 4, "date16")
);

And here's the code:

<?php
//builds an array of relations in format the id1_id2 where
//id2 reports to id1
foreach($employees as $key => $value) {
if($value[2] != $key) {
$relations[] = $value[2] . "_" . $key;
}
}
//sort the array in a natural order
natsort($relations);
//this function builds an array with flat tree structures
//in the format id1_id2_id3_id4_....idx
function make_tree_structure($array) {
$array2 = $array;
$i = 0;
while(list($key, $value) = each($array)) {
$explode = explode("_", $value);
$n = count($explode);
$n = $n - 1;
$under = $explode[$n];
while(list($key2, $value2) = each($array2)) {
if($key != $key2) {
$explode2 = explode("_", $value2);
$n2 = count($explode2) - 1;
$under2 = "";
while($n2 > 0) {
$under2 = $explode2[$n2] . "_" . $under2;
$n2--;
}
$under2 = substr($under2, 0, -1);
$over2 = $explode2[0];
if($over2 == $under) {
$newarray[] = $value . "_" . $under2;
$i = 1;
$x = 1;
unset($array[$key2]);
unset($array2[$key2]);
}
}
}
if($i == 1) {
unset($array[$key]);
unset($array2[$key]);
$i = 0;
}
reset($array2);
}
foreach($array as $value) {
$newarray[] = $value;
}
natsort($newarray);
if($x == 1) {
$newarray = make_tree_structure($newarray);
} else {
$newarray = $array;
}
return $newarray;
}
$flat_tree_structure = make_tree_structure($relations);
//builds a multidimensional array from the flat structures
function build_multidimensional_array($array) {
foreach($array as $value) {
$explode = explode("_", $value);
$string = "";
foreach($explode as $value2) {
$string = $string . "[" . $value2 . "]";
}
$string = "\$newarray" . $string . " = 0;";
eval($string);
}
return $newarray;
}
$tree_structure = build_multidimensional_array($flat_tree_structure) ;
//loops over the multidimensional array and outputs nested lists
function output_nested_lists($array, $employees) {
foreach($array as $key => $value) {
echo "<ul>\n";
echo "<li>" . $employees[$key][1] . "</li>\n"; //You
could change this...
if(is_array($value)) {
output_nested_lists($value, $employees);
}
echo "</ul>\n";
}
}
output_nested_lists($tree_structure, $employees);
?>

Outputs this with the example employees array:

* title1
o title5
+ title4
# title3
* title7
# title6
* title9
o title12
+ title8
# title15
* title2
o title10
+ title16
# title14
* title11
+ title13

If you want the name to be written just use $employees[$key][0] where I
wrote "//You could change this".

Zilla.