Berechnen Verwandtschaft von Genealogischen Daten

StackOverflow https://stackoverflow.com/questions/1063666

Frage

Ich möchte in der Lage sein zu berechnen, die Verwandtschaft zwischen zwei Personen in einem Stammbaum, für die folgende Daten-schema (vereinfacht meine tatsächlichen Daten schema zeigt nur die Spalten, die Sie direkt anwenden, um dieses problem):

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

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

Mit dieser Struktur kann, wie man berechnen Sie die Beziehung zwischen zwei einzelnen id ' s (D. H.cousin, great-grand uncle, etc.).

Auch, da es sind tatsächlich zwei Beziehungen (d.h.A-B kann Neffe in der Erwägung, dass B-A ist Onkel), wie kann man erzeugen, die Ergänzung der anderen (gegeben, Onkel, und angenommen, wir wissen, das Geschlecht, wie könnten wir generieren Neffe?).Dies ist eher eine triviale Frage, die erstere ist das, was ich bin wirklich interessiert.

Vielen Dank an alle!

War es hilfreich?

Lösung 2

Unten ist meine PHP-Implementierung von meinem Algorithmus zur Berechnung Beziehung.Dies basiert auf den Daten-schema habe ich dargestellt in der ursprünglichen Frage.Diese findet die "nächsten", D. H.shortest-path-Beziehung zwischen zwei Individuen, es nicht zu lösen ist zusammengesetzte Beziehungen wie halb-Geschwister oder Doppel-cousins.

Beachten Sie, dass Daten auf die Funktionen zugreifen, wie get_father und get_gender geschrieben im Stil einer Datenbank-Abstraktionsschicht, die ich immer verwenden.Es sollte ziemlich einfach sein, zu verstehen, was Los ist, ist im Grunde alle dbms-spezifischen Funktionen, wie mysql_query ersetzt werden mit verallgemeinerten Funktionen wie db_query;es ist nicht sehr kompliziert, besonders in den Beispielen in diesem code, aber fühlen Sie sich frei, Fragen zu stellen in den Kommentaren, wenn es gar nicht klar.

<?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

?>

Da hatte ich bereits erwähnt, der Algorithmus, um zu bestimmen, LCA, ist weit weniger als optimal.I plan to post a separate Frage zu optimieren, dass, und eine andere, um das problem der Berechnung von zusammengesetzten Beziehungen wie Doppel-cousins.

Vielen Dank an alle, die geholfen prod mir in die richtige Richtung!Mit Ihren Tipps, dies erwies sich als viel einfacher, als ich ursprünglich dachte.

Andere Tipps

Sie werden zunächst die niedrigste gemeinsame Vorfahre sowohl A und B . Rufen Sie diese niedrigste gemeinsame Vorfahre C .

berechnen dann den Abstand in Schritten von C A (CA) und C B (CB ). Diese Werte sollen in einer anderen Tabelle indiziert werden, das die Beziehung zu diesen beiden Werten basiert bestimmt. Zum Beispiel: 

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

Sie können die grundlegenden Beziehungen in dieser Tabelle halten, und „Ur-“ für zusätzliche Strecken auf gewisse Beziehungen wie Großvater, ex hinzufügen .: (0, 3) = Urgroßvater.

Hoffentlich werden Sie in die richtige Richtung weisen. Viel Glück!

UPDATE: (. Ich kann nicht unter Ihren Code kommentieren, da ich noch den Ruf nicht haben)

Ihre Funktion aggrandize_relationships ein wenig aus ist, glaube ich. Sie können es vereinfachen, indem sie „grand“, wenn der Offset-1 oder größer ist, dann das Präfix „Ur-“ (Offset - 1) prefixing mal. Ihre Version könnte das Präfix „Urgroßeltern Urgroßeltern“ für sehr entfernt Verwandte ist. (Nicht sicher, ob ich die richtigen Parameter in dieser Erklärung habe, aber hoffentlich bekommen Sie den Kern von ihm. Auch keine Ahnung, ob Ihr Stammbaum wird, dass weit zurück, aber der Punkt bleibt gültig.)

UPDATE TOO: Sorry, das oben ist falsch. Ich falsch verstanden den Standardfall, und dachte, es rekursiv die Funktion erneut aufgerufen. In meiner Verteidigung, war ich mit der „zweitem Urgroßvater“ Notation nicht vertraut, und immer „Ururgroßvater“ selbst verwendet. Code weiter !!

Dies könnte den Baum Beziehung Rechner helfen ist ein Objekt, das eine XML-Darstellung eines Baumes akzeptiert und wird die Beziehung von zwei beliebigen Mitgliedern innerhalb es berechnet wird. Dieser Artikel beschreibt, wie Beziehungen berechnet werden, und welche Begriffe wie Cousin zweiten Grades oder Cousin ersten Grades einmal entfernt, bedeuten. Dieser Code enthält ein Objekt für die Berechnung der Beziehungen, in JavaScript geschrieben, sowie ein Web-Benutzeroberfläche für das Rendering und mit dem Baum zu interagieren. Das Beispielprojekt ist Setup als klassische ASP-Seite.

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

Ich löste dieses problem mit Nähe list-Konzept in java.Man kann einen Knoten für jede person und sein Kind-Beziehungen verbunden, um es auf dem Knoten selbst.Unten ist der code, nur die Geschwister, Cousins und Cousinen.Jedoch, Sie können verbessern es entsprechend Ihrer Anforderung.Ich schrieb diesen code, der nur für demonstration.

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;
    }

}

Unten ist der Haupt-code zur Familie hinzufügen Menschen zu finden, die Beziehung zu sich selbst.

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.");
}

}

Dies könnte Ihnen helfen, es ist eine Menge Theorie und Implementierung von SQL-Abfragen zu generieren und Abfrage Baumstrukturen

http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

Insbesondere sehen Sie die Adjazenzliste Modell , die verwendet ein Stammbaum als Beispiel.

So seltsam es klingen mag PROLOG scheint die Sache zu sein, die Sie suchen. Gegeben folgende Ad-hoc-Programm ( http://www.pastey.net/117134 bessere Färbung) 

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).

Sie könnten fragen Prolog-Interpreter etwas wie folgt aus: 

relationship(P1, P2, R).

mit den Antworten: 


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.

Es ist ein leistungsfähiges Werkzeug, wenn Sie wissen, wie und wann es zu benutzen. Dies scheint genau wie ein Ort für Prolog. Ich weiß, es ist nicht sehr beliebt, oder einfach zu einbetten, aber das beeindruckende Merkmal wolphram alpha in einen der Kommentare gezeigt, mit nichts mehr als Konstrukte oben verwendet codiert werden, und dies ist Prolog 101

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top