...

View Full Version : Family Tree



NancyJ
07-27-2007, 07:35 PM
I'm trying to output a family tree. I've used recursive function for single parent things - like unlimited recursive menus/submenus. But this is more difficult because of the 2 parents.

I've got a recurring function that gets all the parents but the layout isnt right;

essentially I went a layout like



[child]
[mother] [father]
[maternal grandma][maternal grandpa] [paternal grandma][paternal grandpa]


(but unlimited generations)

currently it looks like

[child]
[mother]
[maternal grandma]
[paternal grandma]
[father]
[maternal grandpa]
[paternal grandpa]

GJay
07-27-2007, 10:00 PM
you're after a breadth-first-search algorithm, completing a level at a time rather than a depth-first-search which completes a branch at a time. It
s made quite a lot easier if you're assuming a single mother and a single father. If you post your code as it stands, it's probably to suggest modifications than to reel off something that bears no relation to your situation.

http://en.wikipedia.org/wiki/Breadth-first_search

NancyJ
07-27-2007, 10:52 PM
yes, single mother and father... not quite sure how it would work any other way ;)


$person = new person();
$person->find($id);

function getParents($child)
{

$child->displayAppearance();

if($child->mum>0)
{
$mum= new person();
$mum->find($child->mum);
getParents($mum);
}

if($child->dad>0)
{
$dad= new person();
$dad->find($child->dad);
getParents($dad);
}

}

NancyJ
07-27-2007, 11:01 PM
I was also wrong about the way the parents were coming out.

Its:

child
mum
mum's mum
mum's dad
dad
dad's mum
dad's dad

but they might not always be symetrical like that, this is another one:

child
mum
mum's mum
mum's dad
dad
dad's mum
dad's mum's mum
dad's mum's dad
dad's dad

firepages
07-28-2007, 02:35 AM
have you ever seen a binary tree representation of data ? ... it looks just like a family tree, google for MPTT and brace yourself, the concept is simple but its implementation less-so.

NancyJ
07-28-2007, 07:06 AM
muahaha, not a problem,
http://www.codingforums.com/showthread.php?t=79773

I love you guys.

NancyJ
07-28-2007, 08:06 AM
Hmmm, that doesn't seem to be working for my problem. I've looked at a bunch of implementations of mptt including marek_mars but they just dont work for me... maybe its worth noting that 'in breeding' is possible - so your father can also be your grandfather etc...
Guess I'll keep plugging away at it.

And also that the tree isnt strictly defined in a database, in that there are many trees in the 1 table. eg all persons are stored in a db but not all persons belong to the same user.

as an example this is a tree of id numbers and in brackets the order they came out in my current function



9(0)
5(1) 8(4)
3(2) 1(3) 5(5) 2(8)
3(6) 1(7)

GJay
07-28-2007, 09:55 AM
function getTree($child,$tail) {
$child->display();

if($child->mum) {
$mum = new Person();
$mum->find($child->mum);
$tail[] = $mum;
}
if($child->dad) {
$dad = new Person();
$dad->find($child->dad);
$tail[] = $dad;
}
getTree(array_shift($tail),$tail);
}

$child = new Person();
$child->find($child_id);
getTree($child,array());


Something like that should do it.

firepages
07-28-2007, 09:57 AM
eg all persons are stored in a db but not all persons belong to the same user.

I get over that by adding an extra field mptt_root, this lets you hold data for different unrelated trees within the same table.

the grandfather-father thing is something else... had not really thought of that.

NancyJ
07-28-2007, 10:06 AM
yay, well, its a step in the right direction, they're out in the right order. Now just need to get the display right in a nice table

NancyJ
07-28-2007, 12:23 PM
Hmmm, plus I need a way to 'fill in the gaps' eg. there is one set of parents in the bottom generation but I have no way to associate the pair with its child

This one is a real head scratcher

dumpfi
07-31-2007, 05:45 PM
This should give you an idea how to solve your task:
<?php
class person
{
private static $allPersons = array();

private
$mother,
$father;

public function __construct($name, $motherId, $fatherId)
{
$this->name = $name;
$this->mother = $motherId;
$this->father = $fatherId;

self::$allPersons[] = $this;
}

public function getFather()
{
return self::find($this->father);
}

public function getMother()
{
return self::find($this->mother);
}

private static function find($id)
{
if(!isset(self::$allPersons[$id]) || $id === NULL)
{
return NULL;
}
return self::$allPersons[$id];
}
}

function displayTree(person $child)
{
// 2 dim array, which holds the persons from each generation
$generations = array();
// holds the persons of a generation, which will be processed
$todo = array($child);
// generation counter
$level = 0;

// construct generations array
do
{
// reset parent array of the current generation
$parents = array();
$i = 0;

// for each person..
while($i < (1<<$level))
{
$person = $todo[$i];
++$i;

// put the person in the generation array
if(!isset($generations[$level]))
{
$generations[$level] = array();
}
$generations[$level][] = $person;

// if a person is NULL, there is no information available for it
if(NULL !== $person)
{
$parents[] = $person->getFather();
$parents[] = $person->getMother();
}
else
{
$parents[] = NULL;
$parents[] = NULL;
}

}

// process the next generation (the parents of the current generation)
$todo = $parents;
++$level;
}
// if there is no information available for any parent of the current generation we stop
while(!isNullArray($parents));

// print table
echo '<table>';

for($i = 0; $i < $level; ++$i)
{

echo '<tr>';

// for each member of the generation..
$count = 1<<$i;
for($j = 0; $j < $count; ++$j)
{
// print name
echo '<td colspan="',(1<<($level - $i)) - 1,'">',
($generations[$i][$j] === NULL) ? 'Unknown' : $generations[$i][$j]->name,
'</td>';
// print an arrow between the parents to show the relationship
if(($j % 2) == 0 && $i)
{
echo '<td>&nbsp;&uarr;&nbsp;</td>';
}
// print an empty field between two parents except for the last
elseif($j != $count - 1)
{
echo '<td>&nbsp;</td>';
}
}

echo '</tr>';
}

echo '</table>';
}

function isNullArray($arr)
{
foreach($arr as $val)
{
if($val !== NULL)
{
return FALSE;
}
}
return TRUE;
}

$child = new person('child', 1, 2);
new person('mother', 3, 4);
new person('father', 5, 6);
new person('mothers mother', 7, 8);
new person('mothers father', 9, 10);
new person('fathers mother', 11, 12);
new person('fathers father', 13, 14);
new person('mothers mothers father', 15, 16);

?>
<html>
<head>
<style type="text/css">
td { width:4em; text-align:center; }
</style>
</head>
<body>
<?php
displayTree($child);
?>
</body>
</html>dumpfi

NancyJ
07-31-2007, 10:40 PM
I actually managed it in the end but the code is on my laptop, I'll post it tomorrow id I remember

NancyJ
08-01-2007, 09:07 PM
This is how it ended up:




$pairs= array();
$ids=0;
$count=0;
$rows = 1;
$pad = 0;
$row=1;
$rowdata = array();

function getTree($child,$tail) {
global $pairs,$count,$rows,$ids, $pad,$rowdata, $row;

$count++;
if($count == pow(2,$row))
{
$row++;
$pad = 0;

}

if($child->mum > 0 ) {
$mum = new person();
$mum->find($child->mum);
$tail[] = $mum;
}
else
{
$tail[]=0;
$pad++;
}

if($child->dad> 0) {
$dad = new person();
$dad->find($child->dad);
$tail[] = $dad;
}
else
{
$tail[] = 0;
$pad++;
}
$pairs[]=array($mum,$dad);
if($pad == pow(2,$row) || $row == 8)
{
}
else
{
getTree(array_shift($tail),$tail);
}
}

getTree($child,array());
$rows = floor(log(count($pairs)+1,2));

echo '<table>';
echo '<tr><td colspan = "'.(pow(2,$rows)).'" align = "center">';
echo '<a href = "view.php?person='.$child->id.'">';
$child->displayImage();
echo '</a>';
echo '</td></tr>';
for($i=0;$i<$rows;$i++)
{
echo '<tr>';
$offset = pow(2,$i)-1;
for($j=$offset; $j<pow(2,$i)+$offset;$j++)
{
if(is_array($pairs[$j]))
{
foreach($pairs[$j] as $pair)
{
$span = pow(2,$rows-$i-1);
echo '<td colspan = "'.$span.'" align="center">';
if(is_object($pair))
{
echo '<a href = "view.php?person='.$pair->id.'">';

$pair->displayImage($i+1);
echo '</a>';
}

echo '</td>';
}
}
}
echo '</tr>';
}
echo '</table>';



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum