Calcular Família Relacionamento de Genealógico de dados
https://stackoverflow.com/questions/1063666
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu gostaria de ser capaz de calcular a relação familiar entre dois indivíduos em uma árvore de família, dado o seguinte esquema de dados (simplificado do meu esquema de dados real, mostrando apenas as colunas que se aplicam diretamente para este problema):
individual
----------
id
gender
child
----------
child_id
father_id
mother_id
Com esta estrutura, como se pode calcular a relação entre dois de id indivíduo (ou seja, primo, grande grande tio, etc.).
Além disso, como há na verdade duas relações (ou seja, A-B pode ser sobrinho enquanto B-A é o tio), como se pode gerar o complemento para o outro (dado tio, e assumindo que sabemos gênero, como podemos gerar sobrinho?). Esta é mais uma questão trivial, o primeiro é o que eu estou realmente interessado em.
Obrigado a todos!
Solução 2
Abaixo está a minha aplicação PHP do meu algoritmo para calcular relacionamento. Esta baseia-se no esquema de dados que descrevi na pergunta original. Isso só encontra o ou seja relacionamento "mais próximo" caminho mais curto entre os dois indivíduos, que não resolve os relacionamentos compostos, tais como meio-irmãos ou primos duplas.
Note que as funções de acesso a dados como get_father e get_gender estão escritos no estilo de uma camada de abstração de banco de dados Eu uso sempre. Deve ser bastante simples de entender o que está acontecendo, basicamente todas as funções específicas do DBMS como mysql_query são substituídos por funções generalizadas, como db_query; Não é muito complicado em tudo, especialmente nos exemplos neste código, mas fique à vontade para postar perguntas nos comentários, se não é clara.
<?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 eu havia mencionado anteriormente, o algoritmo para determinar LCA é muito menos do que ideal. Eu pretendo postar uma pergunta separada para otimizar isso, e outra para resolver o problema de cálculo relacionamentos compostos, tais como primos duplas.
Muito obrigado a todos que ajudaram a prod me na direção certa! Com suas pontas, este acabou por ser muito mais fácil do que eu pensava.
Outras dicas
Você primeiro precisa calcular o mais baixo ancestral comum de ambos A e B . Chame esse mais baixo ancestral comum C .
Em seguida, calcular a distância em passos de C A (CA) e C B (CB ). Estes valores devem ser indexada para uma outra tabela que determina a relação com base nestes dois valores. Por exemplo:
CA CB Relation
1 2 uncle
2 1 nephew
2 2 cousin
0 1 father
0 2 grandfather
Você pode manter as relações básicas nesta tabela, e adicionar "-avô" para distâncias adicionais em certas relações, como avô, ex .: (0, 3) = bisavô.
Esperemos que isto irá apontar na direção certa. Melhor da sorte!
UPDATE: (. Eu não posso comentário abaixo o seu código, uma vez que não têm a reputação ainda)
Seus aggrandize_relationships de função é um pouco fora, eu acho. Você pode simplificá-lo prefixando "grande" se o deslocamento é 1 ou maior, então prefixo "bisavós" (offset - 1) vezes. Sua versão pode incluir o prefixo "grande grande grande grande" para os parentes muito distantes. (Não tenho certeza se eu tenho o parâmetro correto nesta explicação, mas espero que você começa a essência dele. Além disso, nenhuma idéia se sua árvore genealógica vai que longe de volta, mas o ponto permanece válida.)
Atualização TOO: Desculpe, o acima é incorreta. Eu descaracterizou o caso padrão, e pensei que recursivamente chamado a função novamente. Em minha defesa, eu não estava familiarizado com a notação "2nd bisavô", e sempre usou "bisavô" eu mesmo. Código avante !!
Isto pode ajudar a árvore Calculator Relacionamento é um objeto que aceita uma representação XML de uma árvore e irá calcular a relação entre quaisquer dois membros dentro dela. Este artigo descreve como os relacionamentos são calculados, e que termos como primo de segundo grau, ou primo de primeiro grau, uma vez removidos, média. Este código inclui um objeto para relacionamentos de calcular, escritos em JavaScript, bem como uma interface web para renderizar e interagir com a árvore. O projeto de exemplo está configurado como uma página ASP clássico.
http://www.codeproject.com/Articles/30315/Tree- relacionamento-Calculator
Eu resolvi esse problema usando a lista de adjacência conceito em java. Uma pessoa pode ter um nó para cada pessoa e ter suas relações filho associados a ele em seu nó em si. Abaixo está o código para encontrar única irmãos e primos. No entanto, você pode melhorá-lo de acordo com sua exigência. Eu escrevi este código apenas para demonstração.
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;
}
}
Abaixo está o código principal para adicionar pessoas da família e para encontrar relação entre si.
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.");
}
}
Isso pode ajudá-lo, é um monte de teoria e aplicação de consultas SQL para gerar e estruturas de árvore consulta
http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html
Em particular, olhar para o adjacência lista modelo que usos uma árvore de família como exemplo.
Por mais estranho que possa parecer PROLOG parece ser a coisa que você está procurando. Dada a seguir ad-hoc programa ( http://www.pastey.net/117134 melhor coloração)
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).
Você poderia perguntar Prolog intérprete algo assim:
relationship(P1, P2, R).
com as respostas:
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.
É uma ferramenta poderosa, se você sabe como e quando usá-lo. Isso parece exatamente como um lugar para Prolog. Eu sei que não é muito popular, ou fácil de incorporar, mas a característica impressionante de alfa wolphram mostrado em um dos comentários podem ser codificados usando nada mais do que construções usadas acima, e esta é Prolog 101.
