Calcul de parenté famille de données généalogique
https://stackoverflow.com/questions/1063666
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je voudrais être en mesure de calculer la relation familiale entre deux individus dans un arbre généalogique, étant donné le schéma de données (simplifiées de mon schéma de données réelles, ne montrant que les colonnes qui appliquent directement à ce problème):
individual
----------
id
gender
child
----------
child_id
father_id
mother_id
Avec cette structure, comment peut-on calculer la relation entre deux id de personne (par exemple cousin, grand grand-oncle, etc.).
En outre, comme il y a en fait deux relations (à savoir A-B peut être neveu alors que B-A est oncle), comment peut-on générer le complément de l'autre (oncle donné, et en supposant que nous savons genre, comment pourrions-nous créer mon neveu?). Ceci est plus d'une question triviale, le premier est ce que je suis vraiment intéressé.
Merci à tous!
La solution 2
Voici mon implémentation PHP de mon algorithme pour calculer la relation. Ceci est basé sur le schéma de données que je souligné dans la question initiale. Ce ne trouve que le plus « proche » à savoir la relation plus court chemin entre les deux individus, il ne résout pas les relations de composés tels que les demi-frères et sœurs ou doubles cousins.
Notez que les fonctions d'accès aux données telles que et get_father sont écrites dans get_gender le style d'une couche d'abstraction de base de données que j'utilise toujours. Il devrait être assez simple de comprendre ce qui se passe, essentiellement toutes les fonctions spécifiques telles que DBMS sont remplacées par mysql_query fonctions généralisées telles que db_query; il est pas très compliqué du tout, en particulier dans les exemples de ce code, mais ne hésitez pas à poser des questions dans les commentaires si on ne sait pas.
<?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
?>
Comme je l'ai mentionné précédemment, l'algorithme pour déterminer l'ACV est beaucoup moins optimale. Je prévois de poser une question distincte pour optimiser cela, et une autre pour régler le problème du calcul des relations de composés tels que doubles cousins.
Un grand merci à tous ceux qui m'a aidé prod dans la bonne direction! Avec vos conseils, cela se révèle être beaucoup plus facile que je ne le pensais.
Autres conseils
Vous devez d'abord calculer le commun le plus bas Common Ancestor des deux A et B . Appelez ce plus petit commun Ancêtre C .
Puis calculer la distance dans les étapes de C A (CA) et C B (CB ). Ces valeurs doivent être indexées dans une autre table qui détermine la relation de ces deux valeurs. Par exemple:
CA CB Relation
1 2 uncle
2 1 nephew
2 2 cousin
0 1 father
0 2 grandfather
Vous pouvez garder les relations de base dans ce tableau, et ajouter "Great-" pour des distances supplémentaires sur certaines relations comme grand-père, ex .: (0, 3) = grand-père.
Espérons que cela vous pointera dans la bonne direction. Bonne chance!
Mise à jour: (. Je ne peux pas commenter ci-dessous votre code, puisque je n'ai pas encore la réputation)
Votre fonction aggrandize_relationships est un peu loin, je pense. Vous pouvez simplifier par préfixer « grand » si le décalage est 1 ou plus, préfixe puis « Great- » (offset - 1) fois. Votre version peut inclure le préfixe « grand grand grand grand » pour les parents très éloignés. (Je ne sais pas si je le paramètre correct dans cette explication, mais nous espérons que vous obtenez l'essentiel de celui-ci. En outre, aucune idée si votre arbre généalogique va que loin, mais le point reste valable.)
Mise à jour TOO: Désolé, ce qui précède est incorrect. J'ai mal lu le cas par défaut, et je pensais qu'il a appelé à nouveau la fonction récursive. Pour ma défense, je ne connaissais pas la mention « 2ème grand-père », et toujours utilisé moi-même « grand grand-père ». Code en avant !!
Cela pourrait aider l'arbre Relation Calculator est un objet qui accepte une représentation XML d'un arbre et calcule la relation de deux membres en son sein. Cet article décrit comment les relations sont calculés et quels termes comme cousin, ou cousin germain une fois enlevé, signifie. Ce code comprend un objet pour le calcul des relations, écrites en JavaScript, ainsi qu'une interface utilisateur Web pour le rendu et l'interaction avec l'arbre. L'exemple de projet est configuré comme une page ASP classique.
http://www.codeproject.com/Articles/30315/Tree- relation-Calculator
J'ai résolu ce problème en utilisant concept de liste de contiguïté en java. On peut avoir un nœud pour chaque personne et que ses relations enfants qui lui sont associés sur son nœud lui-même. Voici le code pour trouver que frères et soeurs et Cousins. Cependant, vous pouvez l'améliorer en fonction de vos besoins. J'ai écrit ce code uniquement pour la démonstration.
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;
}
}
Voici le code principal pour ajouter des personnes de la famille et de trouver relation entre eux.
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.");
}
}
Cela pourrait vous aider, il y a beaucoup de théorie et mise en œuvre des requêtes SQL pour générer et structures d'arbres de requête
http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html
En particulier, regardez la modèle liste de contiguïté qui utilise un arbre généalogique comme exemple.
Aussi étrange que cela puisse paraître PROLOG semble être la chose que vous recherchez. Compte tenu de la suite du programme ad-hoc ( http://www.pastey.net/117134 une meilleure coloration)
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).
Vous pouvez demander à l'interprète Prolog quelque chose comme ça:
relationship(P1, P2, R).
avec les réponses:
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.
Il est un outil puissant, si vous savez comment et quand l'utiliser. Cela semble exactement comme un endroit pour Prolog. Je sais que ce n'est pas très populaire, ou facile d'intégrer, mais la caractéristique impressionnante de wolphram alpha montré dans l'un des commentaires peuvent être codées en utilisant rien de plus que des constructions utilisées ci-dessus, et c'est Prolog 101.
