"Family Tree" Data Structure

Question

I'm looking for a way to represent a "family tree" (family tree is an elaborate metaphor) in PHP. This means that children will need to inherit from two (or more) parents.

Here are the requirements:

• 1, 2, or more parents
• Bonus points if I can attach metadata like a last name or relationship status

Here is my non-working attempt (no arrays as keys, sadly):

$tree = array(
    'uncle' => false, // no children
    array('mom', 'dad') => array(
        'me' => false,
        array('brother', 'sister-in-law') => array(
            'niece' => false
        )
    )
);

The question is, how can I represent a family tree with these requirements?

Answer 1

You won't be able to do it all in a single array() like that. You can set up trees like that, but setting up more complicated graphs with multiple parents and other relations requires multiple lines of code.

It'll help a lot if you throw some OO at this. Let's create a Person class to help manage the relationships. Fundamentally, we've got people and their relationships with other people, so we'll start there.

Person class

What I imagine is each person having an array of relationships. This array will be indexed first by the type of relationship, for example "parents" or "children". Each entry will then be an array of Persons.

class Person {
    var $name, $relations;

    function __construct($name) {
        $this->name      = $name;
        $this->relations = array();
    }

    function addRelation($type, $person) {
        if (!isset($this->relations[$type])) {
            $this->relations[$type] = array();
        }

        $this->relations[$type][] = $person;
    }

    // Looks up multiple relations, for example "parents".
    function getRelations($type) {
        if (!isset($this->relations[$type])) {
            return array();
        }

        return $this->relations[$type];
    }

    // Looks up a single relation, for example "spouse".
    function getRelation($type) {
        $relations = $this->getRelations($type);
        return empty($relations) ? null : $relations[0];
    }

    function __toString() {
        return $this->name;
    }

Friendly adders and getters

With the above as a foundation we can then add some friendlier-named methods. For illustration we'll handle the parent/child relation and spouses.

    function addParents($mom, $dad) {
        $mom->addChild($this);
        $dad->addChild($this);
    }

    function addChild($child) {
        $this ->addRelation('children', $child);
        $child->addRelation('parents',  $this);
    }

    function addSpouse($spouse) {
        $this  ->addRelation('spouse', $spouse);
        $spouse->addRelation('spouse', $this);
    }

    function getParents () { return $this->getRelations('parents');  }
    function getChildren() { return $this->getRelations('children'); }
    function getSpouse  () { return $this->getRelation ('spouse');   }
}

Creating people

Now we can create a couple of people and setup their relationships. Let's try Billy and his parents John and Jane.

$john  = new Person('John');
$jane  = new Person('Jane');
$billy = new Person('Billy');

$john ->addSpouse ($jane);
$billy->addParents($jane, $john);

And we can check out their relationships like so:

echo "John is married to " . $john->getSpouse() . ".\n";
echo "Billy's parents are " . implode(" and ", $billy->getParents()) . ".\n";

Output:

John is married to Jane.
Billy's parents are Jane and John.

Display family tree

We can traverse the graph recursively if it grows bigger. Here's an example tree-walking function which displays a rudimentary family tree. I've added Sara, her husband Mike, and their son Bobby to the mix.

$john  = new Person('John');
$jane  = new Person('Jane');
$sara  = new Person('Sara');
$mike  = new Person('Mike');
$bobby = new Person('Bobby');
$billy = new Person('Billy');

$john ->addSpouse ($jane);
$sara ->addParents($jane, $john);
$sara ->addSpouse ($mike);
$bobby->addParents($sara, $mike);
$billy->addParents($jane, $john);

function displayFamilyTree($root, $prefix = "") {
    $parents = array($root);

    if ($root->getSpouse() != null) {
        $parents[] = $root->getSpouse();
    }

    echo $prefix . implode(" & ", $parents) . "\n";

    foreach ($root->getChildren() as $child) {
        displayFamilyTree($child, "....$prefix");
    }
}

displayFamilyTree($john);

Output:

John & Jane
....Sara & Mike
........Bobby
....Billy

---

Edit: Here's @Wrikken's comment below, reproduced for readability:

About it indeed. IMHO add a from-until date to every relationship though (possibly NULL for no end). Divorces happen, as do adoptions, etc. Also: I'd add a reverse types & 'ping-back' to the addRelation() function:

function addRelation($type, $person, $reverseType, $pingback = false) {
    if (!isset($this->relations[$type])) {
        $this->relations[$type] = array();
    }

    if (!in_array($person, $this->relations[$type], true)) {
        $this->relations[$type][] = $person;
    }

    if (!$pingback) {
        $person->addRelation($reverseType, $this, $type, true);
    }
}

Answer 2

Good question. Took me a minute to figure that one out.

$tree = array(
        'daughter1' => array(   'name'  => 'Jill',
                                'spouse'    => 'Mike',
                                'children' => array(    'child1' => array(
                                                            ...etc
                                                                    ),
                                                        'child2' => array(
                                                            ...etc
                                                        )
                                                    )
                            ),
        'daughter2' => array(   'name'  => 'Jane',
                                'spouse'    => 'Bob',
                                'children' => array()
                            ),
        'son1'      => array(   'Name'  => 'Ryan',
                                'spouse' => false
                            )
);