계보 데이터에서 가족 관계 계산
https://stackoverflow.com/questions/1063666
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
다음 데이터 스키마를 사용하여 가계도에 있는 두 개인 간의 가족 관계를 계산할 수 있기를 바랍니다(실제 데이터 스키마에서 단순화되어 이 문제에 직접 적용되는 열만 표시).
individual
----------
id
gender
child
----------
child_id
father_id
mother_id
이 구조를 사용하여 두 개의 개별 ID(예:사촌, 증조할아버지 등).
또한 실제로는 두 가지 관계가 있으므로(예:A-B는 조카일 수 있지만 B-A는 삼촌일 수 있습니다. 한 사람이 다른 사람에 대한 보완물을 어떻게 생성할 수 있습니까? (삼촌이 주어지고 성별을 알고 있다고 가정하면 어떻게 조카를 생성할 수 있습니까?)이것은 사소한 질문에 가깝습니다. 전자가 제가 정말로 관심을 갖고 있는 것입니다.
모두 감사합니다!
해결책 2
아래는 관계를 계산하기위한 알고리즘의 PHP 구현입니다. 이것은 원래 질문에 요약 한 데이터 스키마를 기반으로합니다. 이것은 두 개인 사이의 "가장 가까운"즉, 가장 짧은 경로 관계를 발견하며, 반 형제 자매 나 이중 사촌과 같은 복합 관계를 해결하지는 않습니다.
다음과 같은 데이터 액세스 기능 get_father 그리고 get_gender 항상 사용하는 데이터베이스 추상화 계층의 스타일로 작성됩니다. 기본적으로 모든 DBMS 특이 적 함수를 이해하는 것은 상당히 간단해야합니다. mysql_query 다음과 같은 일반화 된 기능으로 대체됩니다 db_query; 특히이 코드의 예제에서는 전혀 복잡하지 않지만 명확하지 않은 경우 의견에 질문을 게시하십시오.
<?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
?>
앞에서 언급했듯이 LCA를 결정하기위한 알고리즘은 최적보다 훨씬 적습니다. 나는 그것을 최적화하기 위해 별도의 질문을 게시 할 계획이며, 다른 하나는 이중 사촌과 같은 복합 관계를 계산하는 문제를 해결하기 위해 다른 질문을 할 계획입니다.
저를 올바른 방향으로 자극하는 모든 분들께 감사드립니다! 당신의 팁으로, 이것은 내가 원래 생각했던 것보다 훨씬 쉬운 것으로 판명되었습니다.
다른 팁
먼저 계산을 해야 합니다. 가장 낮은 공통 조상 둘 다 ㅏ 그리고 비.이것을 가장 낮은 공통 조상이라고 부르세요 씨.
그런 다음 단계적으로 거리를 계산합니다. 씨 에게 ㅏ (캘리포니아) 및 씨 에게 비 (CB).이러한 값은 이 두 값을 기반으로 관계를 결정하는 다른 테이블에 인덱싱되어야 합니다.예를 들어:
CA CB Relation
1 2 uncle
2 1 nephew
2 2 cousin
0 1 father
0 2 grandfather
이 표의 기본 관계를 유지하고 할아버지와 같은 특정 관계에 대한 추가 거리에 대해 "great-"를 추가할 수 있습니다. 예:(0, 3) = 증조할아버지.
이것이 당신에게 올바른 방향을 제시해주기를 바랍니다.행운을 빌어 요!
업데이트: (아직 평판이 없기 때문에 귀하의 코드 아래에 코멘트를 달 수 없습니다.)
귀하의 aggrandize_relationships 기능이 약간 벗어난 것 같습니다.오프셋이 1 이상이면 "grand" 접두사를 붙인 다음 "great-"(오프셋 - 1) 접두사를 붙여서 단순화할 수 있습니다.귀하의 버전에는 매우 먼 친척을 가리키는 접두사 "great grand great grand"가 포함될 수 있습니다.(이 설명에 올바른 매개변수가 있는지는 확실하지 않지만 요점을 이해하시기 바랍니다.또한 귀하의 가계도가 그렇게 멀리까지 거슬러 올라가는지 알 수 없지만 요점은 여전히 유효합니다.)
업데이트도:죄송합니다. 위의 내용이 잘못되었습니다.나는 기본 사례를 잘못 읽었고, 그것이 함수를 다시 재귀적으로 호출한다고 생각했습니다.변명하자면, 저는 "제2증조부" 표기법을 잘 몰랐고, 저도 항상 "고조부"라고만 사용했습니다.앞으로 코드!!
이를 통해 트리 관계 계산기는 트리의 XML 표현을 받아들이고 두 멤버의 관계를 계산하는 객체입니다. 이 기사에서는 관계가 계산되는 방법과 두 번째 사촌 또는 첫 번째 사촌이 일단 제거 된 용어를 설명합니다. 이 코드에는 JavaScript로 작성된 관계 계산을위한 객체와 트리와 렌더링 및 상호 작용을위한 웹 UI가 포함됩니다. 예제 프로젝트는 클래식 ASP 페이지로 설정됩니다.
http://www.codeproject.com/articles/30315/tree-relationship-calculator
Java의 인접력 목록 개념을 사용 하여이 문제를 해결했습니다. 하나는 모든 사람에게 노드를 가질 수 있으며 노드 자체에 아동 관계가 관련 될 수 있습니다. 아래는 형제 자매와 사촌 만 찾는 코드입니다. 그러나 요구 사항에 따라이를 향상시킬 수 있습니다. 나는이 코드를 데모를 위해서만 썼다.
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;
}
}
아래는 가족을 추가하고 그들 사이의 관계를 찾는 주요 코드입니다.
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.");
}
}
이것은 당신에게 도움이 될 수 있습니다. 그것은 트리 구조를 생성하고 쿼리하기위한 SQL 쿼리의 많은 이론과 구현입니다.
http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html
특히, 인접력 목록 모델 가계도를 예로 사용합니다.
프롤로그가 당신이 찾고있는 것 같습니다. 다음과 같은 임시 프로그램이 주어지면 (http://www.pastey.net/117134 더 나은 채색)
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).
Prolog 통역사에게 다음과 같은 것을 물을 수 있습니다.
relationship(P1, P2, R).답과 함께 :
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.
어떻게 사용 방법과시기를 아는 경우 강력한 도구입니다. 이것은 Prolog의 장소와 똑같은 것 같습니다. 나는 그것이 대중적으로 인기가 없거나 포함하기 쉽지 않다는 것을 알고 있지만, 주석 중 하나에 표시된 Wolphram Alpha의 인상적인 특징은 위에 사용 된 구성을 사용하여 코딩 할 수 있으며 Prolog 101입니다.
