php - Estructura de datos "Árbol genealógico"

data-structures family-tree

Question

Estoy buscando una forma de representar un árbol genealógico en PHP. Esto significa que los niños necesitarán heredar de dos (o más) padres.

Aquí están los requisitos:

• 1, 2 o más padres
• Puntos de bonificación si puedo adjuntar metadatos como un apellido o estado de relación

Aquí está mi intento de no trabajo (sin matrices como claves, por desgracia):

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

La pregunta es, ¿cómo puedo representar un árbol genealógico con estos requisitos?

Answer 1

No podrás hacerlo todo en una sola array() así. Puede configurar árboles así, pero la configuración de gráficos más complicados con múltiples padres y otras relaciones requiere múltiples líneas de código.

Te ayudará mucho si le das algo de OO a esto. Creemos una clase Person para ayudar a administrar las relaciones. Fundamentalmente, tenemos personas y sus relaciones con otras personas, entonces comenzaremos allí.

Clase de persona

Lo que imagino es que cada persona tiene una variedad de relaciones. Esta matriz se indexará primero por el tipo de relación, por ejemplo, "padres" o "hijos". Cada entrada será una matriz de Person s.

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

Adders amigables y getters

Con lo anterior como base, podemos agregar algunos métodos más amigables. A modo ilustrativo manejaremos la relación padre / hijo y los cónyuges.

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

Creando personas

Ahora podemos crear un par de personas y configurar sus relaciones. Probemos con Billy y sus padres John y Jane.

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

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

Y podemos verificar sus relaciones de esa manera:

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

Salida:

John está casado con Jane.
Los padres de Billy son Jane y John.

Mostrar árbol genealógico

Podemos atravesar el gráfico recursivamente si crece más. Aquí hay un ejemplo de función de caminar en el árbol que muestra un árbol genealógico rudimentario. He agregado a Sara, su esposo Mike y su hijo Bobby a la mezcla.

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

Salida:

John y Jane
.... Sara y Mike
........Poli
....Porra

Editar: Aquí está el comentario de @ Wrikken a continuación, reproducido para facilitar la lectura:

Sobre eso de hecho Sin embargo, en mi humilde opinión agrego una fecha hasta la fecha para cada relación (posiblemente NULL para un final). Se producen divorcios, al igual que las adopciones, etc. También: agregaría los tipos inversos y ''ping-back'' a la función addRelation() :

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

GEDCOM es una especificación abierta para el intercambio de datos genealógicos entre diferentes programas de genealogía. Un archivo GEDCOM es texto sin formato (generalmente ANSEL o ASCII) que contiene información genealógica sobre individuos y metadatos que vinculan estos registros. La mayoría del software de genealogía admite la importación y / o exportación al formato GEDCOM.

Una ventaja importante de usar GEDCOM sería que podría usar programas de escritorio como Aldfaer (holandés solamente) , Gramps o Legacy Family Tree , así como herramientas en línea como Geneanet para construir o modificar su árbol genealógico y compararlo con los árboles genealógicos de otros .

Otra gran ventaja de utilizar el formato GEDCOM es que hay bibliotecas en múltiples lenguajes de programación a su disposición para guardar y cargar sus datos. Ejemplos de bibliotecas PHP serían GEDCOM Import / Export-Filter , GenealogyGedcom o PHP GEDCOM .

Usando PHP GEDCOM, leer y analizar un archivo GEDCOM sería tan simple como esto:

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

Una desventaja importante del uso de GEDCOM es que el formato de datos de GEDCOM se basa en la familia nuclear, lo que significa que el estándar es limitado en su apoyo a estructuras familiares no tradicionales, como las parejas del mismo sexo, las familias mixtas o la convivencia. Si bien es posible extender GEDCOM para admitir este tipo de relaciones, la interoperabilidad entre diferentes programas está limitada para dichas extensiones.

Otra gran desventaja del uso de GEDCOM es que los archivos GEDCOM son monolíticos. Si tiene un conjunto de datos de miles de personas o quiere cambiar frecuentemente su estructura de datos, es probable que experimente problemas de rendimiento. Especialmente en esos casos, es mejor almacenar sus datos en una base de datos en su lugar. Aún así, eso no significa que GEDCOM sea inútil. En esos casos, es posible que desee considerar el uso de un esquema de base de datos basado en el formato GEDCOM que le permite importar / exportar entre su base de datos y el formato GEDCOM. Para esto, las bibliotecas existen también. Oxy-Gen sería un ejemplo.

Alternativas a GEDCOM serían el modelo de datos de GenTech o el modelo de datos de Gramps . Si bien no se utilizan con tanta frecuencia como el estándar GEDCOM, podrían satisfacer mejor sus necesidades.

Si desea utilizar el modelo de datos de Gramps, puede usar, por ejemplo. el exportador de Gramps PHP para exportar sus datos a una base de datos SQLite. Consulte también esta fuente sobre cómo diseñar su base de datos para que sea adecuada para el modelo de datos de Gramps.