حساب العلاقة الأسرية من الأنساب البيانات
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
مع هذا الهيكل ، كيف يمكن للمرء حساب العلاقة بين اثنين الفردية الهوية (أيابن عم العظيم العم ، إلخ.).
أيضا, كما أن هناك بالفعل اثنين من علاقات (أيأ-ب-قد يكون ابن أخيه حين ب-العم), كيف يمكن توليد تكمل الأخرى (نظرا العم ، وعلى افتراض أننا نعرف الجنس ، كيف يمكننا أن تولد يا ابن أخي؟).هذا هو أكثر من تافهة السؤال السابق هو ما أنا مهتم حقا في.
شكرا جميعا!
المحلول 2
وفيما يلي بلدي تنفيذ PHP خوارزمية بلدي لحساب العلاقة. ويستند هذا على مخطط البيانات أشرت في السؤال الأصلي. هذا يجد سوى "الأقرب" علاقة أي أقصر مسار بين الشخصين، فإنه لا حل العلاقات مركب مثل الأشقاء نصف أو أبناء عمومة مزدوجة.
لاحظ أن وظائف الوصول إلى البيانات مثل مكتوبة get_father وget_gender في أسلوب طبقة قاعدة بيانات التجريد أنا دائما استخدام. يجب أن تكون واضحة إلى حد ما لفهم ما يجري، أساسا يتم استبدال جميع وظائف نظم إدارة قواعد البيانات الخاصة مثل 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 هي أقل بكثير من المستوى الأمثل. أخطط لنشر سؤال منفصل لتحسين ذلك، وآخر لمعالجة مشكلة حساب العلاقات مركب مثل أبناء عمومة مزدوجة.
وشكرا جزيلا لجميع الذين ساعدوا همز لي في الاتجاه الصحيح! مع نصائحك، وتحول هذا إلى أن تكون أسهل بكثير مما كنت اعتقد في البداية.
نصائح أخرى
سوف تحتاج أولا إلى حساب أدنى سلف مشترك كل A و ب.نسمي هذا أدنى سلف مشترك ج.
ثم حساب المسافة في الخطوات من ج إلى A (CA) ، ج إلى ب (CB).هذه القيم يجب أن تكون مفهرسة في آخر الجدول الذي يحدد العلاقة على أساس هذه القيم.على سبيل المثال:
CA CB Relation
1 2 uncle
2 1 nephew
2 2 cousin
0 1 father
0 2 grandfather
كنت قد الحفاظ على العلاقات الأساسية في هذا الجدول و إضافة "كبيرة" على مسافات إضافية على بعض العلاقات مثل جده ، ex.:(0, 3) = الجد.
نأمل أن هذا سوف نقطة لكم في الاتجاه الصحيح.حظا سعيدا!
تحديث: (لا أستطيع التعليق أدناه التعليمات البرمجية الخاصة بك, منذ ليس لدي سمعة بعد.)
وظيفة الخاص بك aggrandize_relationships هو قليلا قبالة ، على ما أعتقد.يمكنك تبسيط ذلك من خلال التقديم "الكبرى" إذا كانت الإزاحة هي 1 أو أكبر ، ثم البادئة "كبيرة" (الإزاحة - 1) مرات.الإصدار الخاص بك قد يشمل البادئة "الكبير الكبير الكبير الكبير" جدا أقارب.(لست متأكدا إذا كان لدي تصحيح المعلمة في هذا التفسير ، ولكن نأمل أن تحصل على جوهر ذلك.أيضا, لا أعرف إذا كانت شجرة العائلة الخاصة بك هو الذهاب إلى وجهة لا تزال سارية المفعول.)
التحديث أيضا: آسف ما سبق غير صحيح.لقد أساء الحالة الافتراضية ، ويعتقد أنه متكرر يسمى وظيفة مرة أخرى.في الدفاع عن بلدي لم أكن على دراية "2 كبير جده" التدوين و تستخدم دائما "الكبير كبير جده" نفسي.رمز فصاعدا!!
وقد تساعد شجرة العلاقة حاسبة هذا هو الكائن الذي يقبل تمثيل XML شجرة وسوف حساب العلاقة بين أي عضوين في داخلها. توضح هذه المقالة كيفية حساب العلاقات، وما مصطلحات مثل ابن عمه الثاني، أو ابن عم إزالة مرة واحدة، يعني. ويشمل هذا الرمز كائن لحساب العلاقات، وكتب في جافا سكريبت، وكذلك واجهة الويب لتقديم والتفاعل مع الشجرة. المشروع مثال على ذلك هو الإعداد كصفحة ASP الكلاسيكية.
وأنا حل هذه المشكلة باستخدام مفهوم القائمة الجوار في جافا. يمكن للمرء أن يكون عقدة لكل شخص ولها علاقات التابعة له المرتبطين به على عقدة في نفسه. فيما يلي رمز للعثور الوحيدة الأشقاء وأبناء العم. ومع ذلك، يمكنك تعزيز هذا التعاون وفقا لمتطلبات الخاص بك. لقد كتبت هذا الرمز فقط للمظاهرة.
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
وعلى وجه الخصوص، أن ننظر في قائمة الجوار نموذج الذي يستخدم شجرة العائلة كمثال.
وكما غريبا كما قد يبدو PROLOG يبدو أن الشيء الذي تبحث عنه. نظرا التالية برنامج ( 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).
هل يمكن أن نسأل حاسوب مترجم شيء من هذا القبيل:
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.
وإنها أداة قوية، إذا كنت تعرف كيف ومتى لاستخدامها. هذا يبدو تماما مثل مكان للحاسوب. أنا أعلم أنها ليست شعبية بشكل رهيب، أو من السهل تضمين، ولكن ميزة رائعة من ألفا wolphram هو مبين في واحدة من التعليقات التي يمكن ترميزها باستخدام أي شيء أكثر من بنيات المستخدمة أعلاه، وهذا هو حاسوب 101.
