"Family Tree" Data Structure

I'm looking for a way to represent a family tree in PHP. This means that children will need to inherit from tw开发者_高级运维o (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?

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);
    }
}

GEDCOM is an open specification for exchanging genealogical data between different genealogy software. A GEDCOM file is plain text (usually either ANSEL or ASCII) containing genealogical information about individuals, and meta data linking these records together. Most genealogy software supports importing from and/or exporting to GEDCOM format.

A major advantage of using GEDCOM, would be that you could use desktop programs like Aldfaer (Dutch only), Gramps or Legacy Family Tree as well as online tools like Geneanet to build or modify your family tree and compare it with the family trees of others.

Another major advantage of using the GEDCOM format, is that there are libraries in multiple programming language at your disposal to save and load your data. Examples of PHP libraries would be GEDCOM Import/Export-Filter, GenealogyGedcom or PHP GEDCOM.

Using PHP GEDCOM, reading and parsing a GEDCOM file would be as simple as this:

$parser = new \PhpGedcom\Parser();
$gedcom = $parser->parse('gedcom.ged');

A major disadvantage of using GEDCOM, is that GEDCOM's data format is built around the nuclear family, which means that the standard is limited in its support of non-traditional family structures, like same-sex partnerships, blended families or cohabitation. While it is possible to extend GEDCOM to support this type of relationships, inter-operability between different software is limited for such extensions.

Another major disadvantage of using GEDCOM, is that GEDCOM files are monolithic. If you have a dataset of thousands of people or your want to frequently change your data structure, you're likely to experience performance problems. Especially in those cases, it's best to store your data in a database instead. Still, that doesn't mean GEDCOM is useless. In those cases, you might want to consider using a database schema based on the GEDCOM format that allows you to import/export between your database and the GEDCOM format. For this, libraries exist as well. Oxy-Gen would be an example.

Alternatives to GEDCOM would be GenTech's data model or Gramps data model. While they aren't as commonly used as the GEDCOM standard, they might better suit your needs.

If you want to use the Gramps data model, you can use eg. the Gramps PHP exporter to export your data into an SQLite database. See also this source on how to design your database to be suitable for the Gramps data model.