php - "Family Tree"数据结构

Question

我正在寻找一种在 PHP 中表示家谱的方法。这意味着 child 需要从两个(或更多) parent 那里继承。

要求如下:

• 1、2 或更多 parent
• 如果我可以附上姓氏或关系状态等元数据，可加分

这是我的无效尝试(遗憾的是没有数组作为键):

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

问题是，我如何表示具有这些要求的家谱？

Answer 1

您无法像那样在单个 array() 中完成所有操作。您可以像那样设置树，但设置具有多个父项和其他关系的更复杂的图需要多行代码。

如果您对此进行一些 OO 处理，将会大有帮助。让我们创建一个 Person 类来帮助管理关系。从根本上说，我们已经有了人以及他们与其他人的关系，所以我们将从这里开始。

人物类

我想象的是每个人都有一系列的关系。该数组将首先按关系类型进行索引，例如“ parent ”或“ child ”。然后每个条目将是一个 Person 数组。

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

友好的加法器和 setter/getter

以上述为基础，我们可以添加一些更友好命名的方法。为了便于说明，我们将处理 parent /子女关系和配偶。

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

创造人

现在我们可以创建几个人并设置他们的关系。让我们试试 Billy 和他的 parent John 和 Jane。

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

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

我们可以像这样检查他们的关系:

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

输出:

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

显示家谱

如果图变大，我们可以递归遍历图。下面是一个显示基本家谱的树遍历函数示例。我已经将 Sara、她的丈夫 Mike 和他们的儿子 Bobby 添加到组合中。

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

输出:

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

---

编辑:下面是@Wrikken 的评论，为了便于阅读，转载了:

确实如此。恕我直言，为每个关系添加一个从-到日期(可能是 NULL 表示没有结束)。离婚和收养等都会发生。此外:我会向 addRelation() 函数添加反向类型和“ping-back”:

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