Calcular la relación familiar a partir de datos genealógicos
https://stackoverflow.com/questions/1063666
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Me gustaría poder calcular la relación familiar entre dos personas en un árbol genealógico, dado el siguiente esquema de datos (simplificado de mi esquema de datos real, que solo muestra columnas que se aplican directamente a este problema):
individual
----------
id
gender
child
----------
child_id
father_id
mother_id
Con esta estructura, ¿cómo se puede calcular la relación entre dos identificaciones individuales (es decir,primo, tío bisabuelo, etc.).
Además, como en realidad hay dos relaciones (es decir,A-B puede ser sobrino mientras que B-A es tío), ¿cómo se puede generar el complemento para el otro (dado el tío, y asumiendo que conocemos el género, cómo podríamos generar sobrino?).Esta es una pregunta más trivial, la primera es lo que realmente me interesa.
¡Gracias a todos!
Solución 2
A continuación se muestra mi implementación PHP de mi algoritmo para calcular la relación.Esto se basa en el esquema de datos que describí en la pregunta original.Esto sólo encuentra el "más cercano", es decirrelación de camino más corto entre dos individuos, no resuelve relaciones compuestas como medio hermanos o primos dobles.
Tenga en cuenta que las funciones de acceso a datos como get_father y get_gender están escritos en el estilo de una capa de abstracción de base de datos que siempre uso.Debería ser bastante sencillo entender lo que está pasando, básicamente todas las funciones específicas de dbms, como mysql_query se reemplazan con funciones generalizadas como db_query;No es nada complicado, especialmente en los ejemplos de este código, pero no dudes en publicar preguntas en los comentarios si no queda claro.
<?php
/* Calculate relationship "a is the ___ of b" */
define("GENDER_MALE", 1);
define("GENDER_FEMALE", 2);
function calculate_relationship($a_id, $b_id)
{
if ($a_id == $b_id) {
return 'self';
}
$lca = lowest_common_ancestor($a_id, $b_id);
if (!$lca) {
return false;
}
$a_dist = $lca[1];
$b_dist = $lca[2];
$a_gen = get_gender($a_id);
// DIRECT DESCENDANT - PARENT
if ($a_dist == 0) {
$rel = $a_gen == GENDER_MALE ? 'father' : 'mother';
return aggrandize_relationship($rel, $b_dist);
}
// DIRECT DESCENDANT - CHILD
if ($b_dist == 0) {
$rel = $a_gen == GENDER_MALE ? 'son' : 'daughter';
return aggrandize_relationship($rel, $a_dist);
}
// EQUAL DISTANCE - SIBLINGS / PERFECT COUSINS
if ($a_dist == $b_dist) {
switch ($a_dist) {
case 1:
return $a_gen == GENDER_MALE ? 'brother' : 'sister';
break;
case 2:
return 'cousin';
break;
default:
return ordinal_suffix($a_dist - 2).' cousin';
}
}
// AUNT / UNCLE
if ($a_dist == 1) {
$rel = $a_gen == GENDER_MALE ? 'uncle' : 'aunt';
return aggrandize_relationship($rel, $b_dist, 1);
}
// NEPHEW / NIECE
if ($b_dist == 1) {
$rel = $a_gen == GENDER_MALE ? 'nephew' : 'niece';
return aggrandize_relationship($rel, $a_dist, 1);
}
// COUSINS, GENERATIONALLY REMOVED
$cous_ord = min($a_dist, $b_dist) - 1;
$cous_gen = abs($a_dist - $b_dist);
return ordinal_suffix($cous_ord).' cousin '.format_plural($cous_gen, 'time', 'times').' removed';
} //END function calculate_relationship
function aggrandize_relationship($rel, $dist, $offset = 0) {
$dist -= $offset;
switch ($dist) {
case 1:
return $rel;
break;
case 2:
return 'grand'.$rel;
break;
case 3:
return 'great grand'.$rel;
break;
default:
return ordinal_suffix($dist - 2).' great grand'.$rel;
}
} //END function aggrandize_relationship
function lowest_common_ancestor($a_id, $b_id)
{
$common_ancestors = common_ancestors($a_id, $b_id);
$least_distance = -1;
$ld_index = -1;
foreach ($common_ancestors as $i => $c_anc) {
$distance = $c_anc[1] + $c_anc[2];
if ($least_distance < 0 || $least_distance > $distance) {
$least_distance = $distance;
$ld_index = $i;
}
}
return $ld_index >= 0 ? $common_ancestors[$ld_index] : false;
} //END function lowest_common_ancestor
function common_ancestors($a_id, $b_id) {
$common_ancestors = array();
$a_ancestors = get_ancestors($a_id);
$b_ancestors = get_ancestors($b_id);
foreach ($a_ancestors as $a_anc) {
foreach ($b_ancestors as $b_anc) {
if ($a_anc[0] == $b_anc[0]) {
$common_ancestors[] = array($a_anc[0], $a_anc[1], $b_anc[1]);
break 1;
}
}
}
return $common_ancestors;
} //END function common_ancestors
function get_ancestors($id, $dist = 0)
{
$ancestors = array();
// SELF
$ancestors[] = array($id, $dist);
// PARENTS
$parents = get_parents($id);
foreach ($parents as $par) {
if ($par != 0) {
$par_ancestors = get_ancestors($par, $dist + 1);
foreach ($par_ancestors as $par_anc) {
$ancestors[] = $par_anc;
}
}
}
return $ancestors;
} //END function get_ancestors
function get_parents($id)
{
return array(get_father($id), get_mother($id));
} //END function get_parents
function get_father($id)
{
$res = db_result(db_query("SELECT father_id FROM child WHERE child_id = %s", $id));
return $res ? $res : 0;
} //END function get_father
function get_mother($id)
{
$res = db_result(db_query("SELECT mother_id FROM child WHERE child_id = %s", $id));
return $res ? $res : 0;
} //END function get_mother
function get_gender($id)
{
return intval(db_result(db_query("SELECT gender FROM individual WHERE id = %s", $id)));
}
function ordinal_suffix($number, $super = false)
{
if ($number % 100 > 10 && $number %100 < 14) {
$os = 'th';
} else if ($number == 0) {
$os = '';
} else {
$last = substr($number, -1, 1);
switch($last) {
case "1":
$os = 'st';
break;
case "2":
$os = 'nd';
break;
case "3":
$os = 'rd';
break;
default:
$os = 'th';
}
}
$os = $super ? '<sup>'.$os.'</sup>' : $os;
return $number.$os;
} //END function ordinal_suffix
function format_plural($count, $singular, $plural)
{
return $count.' '.($count == 1 || $count == -1 ? $singular : $plural);
} //END function plural_format
?>
Como mencioné anteriormente, el algoritmo para determinar el ACV dista mucho de ser óptimo.Planeo publicar una pregunta separada para optimizar eso y otra para abordar el problema de calcular relaciones compuestas como primos dobles.
¡Muchas gracias a todos los que me ayudaron a orientarme en la dirección correcta!Con tus consejos, esto resultó ser mucho más fácil de lo que pensaba originalmente.
Otros consejos
primero tendrá que calcular el bajo antepasado común tanto de y B . Llame a este antepasado común más bajo C .
A continuación, calcular la distancia en pasos de C a A (CA) y C a B (CB ). Estos valores deben ser indexados en otra tabla que determina la relación basada en estos dos valores. Por ejemplo:
CA CB Relation
1 2 uncle
2 1 nephew
2 2 cousin
0 1 father
0 2 grandfather
Es posible mantener las relaciones básicas en esta tabla, y añadir "estupendo," para distancias adicionales en ciertas relaciones, como abuelo, ex .: (0, 3) = bisabuelo.
Esperamos que esto le apuntan en la dirección correcta. Mejor de las suertes!
ACTUALIZACIÓN: (. No puedo comentar por debajo de su código, ya no tengo la reputación aún)
Sus aggrandize_relationships función es un poco apagado, creo. Se puede simplificar con el prefijo "gran" si el desplazamiento es 1 o mayor, entonces prefijo "genial-" (Offset - 1) veces. Su versión podría incluir el prefijo "gran gran gran gran" para los parientes muy lejanos. (No estoy seguro si tengo el parámetro correcto en esta explicación, pero es de esperar que llegue la esencia de la misma. Además, ni idea de si su árbol genealógico va ese más atrás, pero el punto sigue siendo válido.)
ACTUALIZACIÓN también: Lo sentimos, lo anterior es incorrecta. Leí mal el caso por defecto, y pensé que de forma recursiva llama de nuevo la función. En mi defensa, no estaba familiarizado con la notación "segunda bisabuelo", y siempre solía "tatarabuelo" mí mismo. Código en adelante !!
Esto podría ayudar al árbol de relaciones Calculator es un objeto que acepte una representación XML de un árbol y calculará la relación de los dos miembros que la integran. En este artículo se describe cómo se calculan las relaciones, y lo que términos como primo segundo, o el primer primo quitado una vez, significan. Este código incluye un objeto para las relaciones de calcular, escritos en JavaScript, así como una interfaz web para la representación y la interacción con el árbol. El proyecto de ejemplo se configura como una página ASP clásico.
http://www.codeproject.com/Articles/30315/Tree- relación-Calculadora
He resuelto este problema utilizando el concepto lista de adyacencia en Java. Uno puede tener un nodo para cada persona y tienen sus relaciones dependientes asociados a ella en su propio nodo. A continuación se muestra el código para encontrar sólo hermanos y primos. Sin embargo, puede mejorar de acuerdo a su requerimiento. Escribí este código sólo para demostración.
public class Person {
String name;
String gender;
int age;
int salary;
String fatherName;
String motherName;
public Person(String name, String gender, int age, int salary, String fatherName,
String motherName) {
super();
this.name = name;
this.gender = gender;
this.age = age;
this.salary = salary;
this.fatherName = fatherName;
this.motherName = motherName;
}
}
A continuación se muestra el código principal para agregar las personas de la familia y encontrar relación entre ellos.
import java.util.LinkedList;
public class PeopleAndRelationAdjacencyList {
private static String MALE = "male";
private static String FEMALE = "female";
public static void main(String[] args) {
int size = 25;
LinkedList<Person> adjListArray[] = new LinkedList[size];
for (int i = 0; i < size; i++) {
adjListArray[i] = new LinkedList<>();
}
addPerson( adjListArray, "GGM1", MALE, null, null );
addPerson( adjListArray, "GGF1", FEMALE, null, null );
addPerson( adjListArray, "GM1", MALE, "GGM1", "GGF1" );
addPerson( adjListArray, "GM2", MALE, "GGM1", "GGF1" );
addPerson( adjListArray, "GM1W", FEMALE, null, null );
addPerson( adjListArray, "GM2W", FEMALE, null, null );
addPerson( adjListArray, "PM1", MALE, "GM1", "GM1W" );
addPerson( adjListArray, "PM2", MALE, "GM1", "GM1W" );
addPerson( adjListArray, "PM3", MALE, "GM2", "GM2W" );
addPerson( adjListArray, "PM1W", FEMALE, null, null );
addPerson( adjListArray, "PM2W", FEMALE, null, null );
addPerson( adjListArray, "PM3W", FEMALE, null, null );
addPerson( adjListArray, "S1", MALE, "PM1", "PM1W" );
addPerson( adjListArray, "S2", MALE, "PM2", "PM2W" );
addPerson( adjListArray, "S3", MALE, "PM3", "PM3W" );
addPerson( adjListArray, "S4", MALE, "PM3", "PM3W" );
printGraph(adjListArray);
System.out.println("Done !");
getRelationBetweenPeopleForGivenNames(adjListArray, "S3", "S4");
getRelationBetweenPeopleForGivenNames(adjListArray, "S1", "S2");
}
private static void getRelationBetweenPeopleForGivenNames(LinkedList<Person>[] adjListArray, String name1, String name2) {
if ( adjListArray[getIndexOfGivenNameInHeadPositionOfList(adjListArray, name1)].peekFirst().fatherName
.equalsIgnoreCase(
adjListArray[getIndexOfGivenNameInHeadPositionOfList(adjListArray, name2)].peekFirst().fatherName) ) {
System.out.println("SIBLIGS");
return;
}
String name1FatherName = adjListArray[getIndexOfGivenNameInHeadPositionOfList(adjListArray, name1)].peekFirst().fatherName;
String name2FatherName = adjListArray[getIndexOfGivenNameInHeadPositionOfList(adjListArray, name2)].peekFirst().fatherName;
if ( adjListArray[getIndexOfGivenNameInHeadPositionOfList(adjListArray, name1FatherName)].peekFirst().fatherName
.equalsIgnoreCase(
adjListArray[getIndexOfGivenNameInHeadPositionOfList(adjListArray, name2FatherName)].peekFirst().fatherName) ) {
System.out.println("COUSINS");
}
}
private static void addPerson(LinkedList<Person>[] adjListArray, String name, String gender, String fatherName, String motherName) {
Person person = new Person(name, gender, 0, 0, fatherName, motherName);
int indexToPutperson = getEmptyIndexInAdjListToInserterson(adjListArray);
adjListArray[indexToPutperson].addLast(person);
if( fatherName!=null ){
int indexOffatherName = getIndexOfGivenNameInHeadPositionOfList( adjListArray, fatherName);
adjListArray[indexOffatherName].addLast(person);
}
if( motherName!=null ){
int indexOfMotherName = getIndexOfGivenNameInHeadPositionOfList( adjListArray, motherName);
adjListArray[indexOfMotherName].addLast(person);
}
}
private static int getIndexOfGivenNameInHeadPositionOfList( LinkedList<Person>[] adjListArray, String nameToBeSearched ) {
for (int i = 0; i < adjListArray.length; i++) {
if( adjListArray[i] != null ){
if(adjListArray[i].peekFirst() != null){
if(adjListArray[i].peekFirst().name.equalsIgnoreCase(nameToBeSearched)){
return i;
}
}
}
}
// handle if father name is not found
return 0;
}
private static void printGraph(LinkedList<Person>[] adjListArray) {
for (int v = 0; v < 15; v++) {
System.out.print("head");
LinkedList<Person> innerLinkedList = adjListArray[v];
for (int i = 0; i < innerLinkedList.size(); i++) {
Person person = innerLinkedList.get(i);
System.out.print(" -> " + person.name);
}
System.out.println("\n");
}
}
private static int getEmptyIndexInAdjListToInserterson( LinkedList<Person>[] adjListArray) {
for (int i = 0; i < adjListArray.length; i++) {
if(adjListArray[i].isEmpty()){
return i;
}
}
throw new IndexOutOfBoundsException("List of relation is full.");
}
}
Esto podría ayudarle, es mucha teoría e implementación de consultas SQL para generar y consultar estructuras de árbol.
http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html
En particular, mire el modelo de lista de adyacencia que utiliza un árbol genealógico como ejemplo.
Por extraño que pueda parecer PROLOG parece ser lo que usted está buscando. Dada siguiente ad-hoc programa ( http://www.pastey.net/117134 mejor colorante)
female(alice).
female(eve).
female(kate).
male(bob).
male(carlos).
male(dave).
% mother(_mother, _child).
mother(alice, bob).
mother(kate, alice).
% father(_father, _child)
father(carlos, bob).
child(C, P) :- father(P, C).
child(C, P) :- mother(P, C).
parent(X, Y) :- mother(X, Y).
parent(X, Y) :- father(X, Y).
sister(alice, eve).
sister(eve, alice).
sister(alice, dave).
brother(dave, alice).
% brother(sibling, sibling)
sibling(X, Y) :- brother(X, Y).
sibling(X, Y) :- sister(X, Y).
uncle(U, C) :- sibling(U, PARENT),
child(C, PARENT),
male(U).
relationship(U, C, uncle) :- uncle(U, C).
relationship(P, C, parent) :- parent(P, C).
relationship(B, S, brother) :- brother(B, S).
relationship(G, C, grandparent) :- parent(P, C), parent(G, P).
Se puede pedir Prolog intérprete algo así:
relationship(P1, P2, R).
con las respuestas:
P1 = dave, P2 = bob, R = uncle ;
P1 = alice, P2 = bob, R = parent ;
P1 = kate, P2 = alice, R = parent ;
P1 = carlos, P2 = bob, R = parent ;
P1 = dave, P2 = alice, R = brother ;
P1 = kate, P2 = bob, R = grandparent ;
false.
Es una herramienta poderosa, si usted sabe cómo y cuándo usarlo. Esto parece exactamente igual que un lugar para Prolog. Yo sé que no es terriblemente popular o fácil de encajar, pero la característica impresionante de wolphram alfa se muestra en uno de los comentarios se pueden codificar usando nada más que construcciones utilizadas anteriormente, y esto es Prolog 101.
