Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 14 of 14

Thread: Family Tree

  1. #1
    Senior Coder NancyJ's Avatar
    Join Date
    Feb 2005
    Location
    Bradford, UK
    Posts
    3,174
    Thanks
    19
    Thanked 66 Times in 65 Posts

    Family Tree

    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

    Code:
                                                     [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]

  • #2
    Senior Coder
    Join Date
    Sep 2005
    Posts
    1,791
    Thanks
    5
    Thanked 36 Times in 35 Posts
    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
    My thoughts on some things: http://codemeetsmusic.com
    And my scrapbook of cool things: http://gjones.tumblr.com

  • #3
    Senior Coder NancyJ's Avatar
    Join Date
    Feb 2005
    Location
    Bradford, UK
    Posts
    3,174
    Thanks
    19
    Thanked 66 Times in 65 Posts
    yes, single mother and father... not quite sure how it would work any other way
    PHP Code:
    $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); 
     }



  • #4
    Senior Coder NancyJ's Avatar
    Join Date
    Feb 2005
    Location
    Bradford, UK
    Posts
    3,174
    Thanks
    19
    Thanked 66 Times in 65 Posts
    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

  • #5
    Super Moderator
    Join Date
    May 2002
    Location
    Perth Australia
    Posts
    4,044
    Thanks
    10
    Thanked 93 Times in 91 Posts
    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.
    resistance is...

    MVC is the current buzz in web application architectures. It comes from event-driven desktop application design and doesn't fit into web application design very well. But luckily nobody really knows what MVC means, so we can call our presentation layer separation mechanism MVC and move on. (Rasmus Lerdorf)

  • #6
    Senior Coder NancyJ's Avatar
    Join Date
    Feb 2005
    Location
    Bradford, UK
    Posts
    3,174
    Thanks
    19
    Thanked 66 Times in 65 Posts
    muahaha, not a problem,
    MPTT Class

    I love you guys.

  • #7
    Senior Coder NancyJ's Avatar
    Join Date
    Feb 2005
    Location
    Bradford, UK
    Posts
    3,174
    Thanks
    19
    Thanked 66 Times in 65 Posts
    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

    Code:
                  9(0)
        5(1)                  8(4)
    3(2)   1(3)           5(5)      2(8)
                       3(6)  1(7)
    Last edited by NancyJ; 07-28-2007 at 08:28 AM.

  • #8
    Senior Coder
    Join Date
    Sep 2005
    Posts
    1,791
    Thanks
    5
    Thanked 36 Times in 35 Posts
    PHP Code:
    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.
    My thoughts on some things: http://codemeetsmusic.com
    And my scrapbook of cool things: http://gjones.tumblr.com

  • #9
    Super Moderator
    Join Date
    May 2002
    Location
    Perth Australia
    Posts
    4,044
    Thanks
    10
    Thanked 93 Times in 91 Posts
    Quote Originally Posted by NancyJ View Post
    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.
    resistance is...

    MVC is the current buzz in web application architectures. It comes from event-driven desktop application design and doesn't fit into web application design very well. But luckily nobody really knows what MVC means, so we can call our presentation layer separation mechanism MVC and move on. (Rasmus Lerdorf)

  • #10
    Senior Coder NancyJ's Avatar
    Join Date
    Feb 2005
    Location
    Bradford, UK
    Posts
    3,174
    Thanks
    19
    Thanked 66 Times in 65 Posts
    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

  • #11
    Senior Coder NancyJ's Avatar
    Join Date
    Feb 2005
    Location
    Bradford, UK
    Posts
    3,174
    Thanks
    19
    Thanked 66 Times in 65 Posts
    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

  • #12
    Regular Coder
    Join Date
    Jun 2004
    Posts
    565
    Thanks
    0
    Thanked 18 Times in 18 Posts
    This should give you an idea how to solve your task:
    PHP Code:
    <?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) == && $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'12);
    new 
    person('mother'34);
    new 
    person('father'56);
    new 
    person('mothers mother'78);
    new 
    person('mothers father'910);
    new 
    person('fathers mother'1112);
    new 
    person('fathers father'1314);
    new 
    person('mothers mothers father'1516);

    ?>
    <html>
        <head>
            <style type="text/css">
            td { width:4em; text-align:center; }
            </style>
        </head>
        <body>
        <?php
        displayTree
    ($child);
        
    ?>
        </body>
    </html>
    dumpfi
    Last edited by dumpfi; 07-31-2007 at 05:57 PM.
    "Failure is not an option. It comes bundled with the software."
    ....../)/)..(\__/).(\(\................../)_/)......
    .....(-.-).(='.'=).(-.-)................(o.O)...../<)
    ....(.).(.)("}_("}(.)(.)...............(.)_(.))Ż/.
    ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ
    Little did the bunnies suspect that one of them was a psychotic mass murderer with a 6 ft. axe.

  • #13
    Senior Coder NancyJ's Avatar
    Join Date
    Feb 2005
    Location
    Bradford, UK
    Posts
    3,174
    Thanks
    19
    Thanked 66 Times in 65 Posts
    I actually managed it in the end but the code is on my laptop, I'll post it tomorrow id I remember

  • #14
    Senior Coder NancyJ's Avatar
    Join Date
    Feb 2005
    Location
    Bradford, UK
    Posts
    3,174
    Thanks
    19
    Thanked 66 Times in 65 Posts
    This is how it ended up:

    PHP Code:

    $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 ) {
         
    $mum = new person();
         
    $mum->find($child->mum);
         
    $tail[] = $mum;          
       }
       else
       {
        
    $tail[]=0;
        
    $pad++;
      }

       if(
    $child->dad0) {
          
    $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>'


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •