从谱系数据计算家庭关系

Question

我希望能够计算家谱中两个人之间的家庭关系,给定以下数据模式(从我的实际数据模式简化,仅显示直接适用于此问题的列):

individual
----------
id
gender

child
----------
child_id
father_id
mother_id

通过这种结构,如何计算两个个体id(即堂兄,大叔叔等)之间的关系.

另外,由于实际上有两种关系(即AB可能是侄子而BA是叔叔),如何生成另一种的补充(给定叔叔,并假设我们知道性别,我们如何生成侄子？).这是一个微不足道的问题,前者是我真正感兴趣的.

谢谢大家!

Answer 1

首先,您需要计算出最低共同祖先两者的一个和乙.调用此最近公共祖先Ç.

然后计算从C到A(CA)和C到B(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-"(offset - 1)前缀,可以简化它.你的版本可能包括非常远的亲戚的前缀"伟大的伟大的伟大".(不知道我在这个解释中是否有正确的参数,但希望你得到它的要点.另外,不知道你的家谱是否正在很久以前,但这一点仍然有效.)

更新 太:抱歉,以上内容不正确.我误读了默认情况,并认为它再次以递归方式调用了该函数.在我的辩护中,我不熟悉"第二个曾祖父"的表示法,并且自己总是使用"伟大的曾祖父".代码向前!!

Answer 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的算法远不是最优的.我打算发布一个单独的问题来优化它,另一个解决计算复合关系的问题,如双表兄弟.

非常感谢所有帮助我朝着正确方向前进的人!根据您的提示,这比我原先想象的要容易得多.