根据家谱数据计算家庭关系

下面是我用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

?>

正如我之前提到的,确定生命周期评价的算法远不是最优的。我计划发布一个单独的问题来优化它,另一个问题来解决计算复合关系(如双表兄妹)的问题。

非常感谢所有帮助我朝着正确方向前进的人!有了你的建议,这比我最初想象的要容易得多。

您首先需要计算 Lowest Common Ancestor 两者皆有 A. 和 B 称之为最低级的共同祖先 .

到 A. (CA)和 到 B

CA      CB      Relation
1       2       uncle
2       1       nephew
2       2       cousin
0       1       father
0       2       grandfather

您可以保留此表中的基本关系,并在某些关系上添加“great-”以表示额外的距离,例如祖父,例如:(0,3)=曾祖父。

更新: (我不能在你的代码下面发表评论,因为我还没有这个名声。)

也更新: 对不起,以上内容不正确。我误读了默认情况,以为它会再次递归调用函数。在我的辩护中,我不熟悉“第二曾祖父”的符号,我自己总是使用“曾曾祖父”。代码前进!!

http://www.codeproject.com/Articles/30315/Tree-Relationship-Calculator

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

adjacency list model 其使用家谱作为示例。

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.