Calcola Family Relationship da Genealogical dati

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

Domanda

Mi piacerebbe essere in grado di calcolare il rapporto di parentela tra due individui in un albero di famiglia, dato il seguente schema di dati (semplificato dal mio schema di dati reali, mostrando solo le colonne che si applicano direttamente a questo problema): 

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

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

Con questa struttura, come si può calcolare il rapporto tra due di id individuale (cioè cugino, grande grande zio, ecc.).

Inoltre, come ci sono in realtà due relazioni (vale a dire A-B può essere nipote mentre B-A è lo zio), come si può generare il complemento all'altro (dato lo zio, e assumendo sappiamo genere, come potremmo generare nipote?). Questo è più di una domanda banale, il primo è quello che mi interessa veramente.

Grazie a tutti!

È stato utile?

Soluzione 2

Di seguito è la mia implementazione di PHP del mio algoritmo per calcolare rapporto. Questo si basa sullo schema dei dati ho descritto nella domanda iniziale. Ciò trova solo il rapporto cioè percorso minimo "vicini" tra i due individui, non risolve rapporti composti come fratellastri o doppi cugini.

Si noti che le funzioni di accesso ai dati, come get_father e get_gender sono scritti nello stile di uno strato di astrazione del database che uso sempre. Dovrebbe essere abbastanza semplice per capire cosa sta succedendo, in pratica tutti i-specifico DBMS funzioni quali mysql_query vengono sostituiti con funzioni generalizzate quali db_query; non è molto complicato a tutti, in particolare negli esempi di questo codice, ma sentitevi liberi di inviare domande nei commenti, se non è chiaro. 

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

?>

Come avevo accennato in precedenza, l'algoritmo per determinare LCA è molto meno che ottimale. Ho intenzione di inviare una domanda separata per ottimizzare questo, e un altro per affrontare il problema del calcolo rapporti composti quali doppi cugini.

Molte grazie a tutti coloro che mi ha aiutato a prod nella direzione giusta! Con i vostri suggerimenti, questo si è rivelato essere molto più facile di quanto inizialmente pensato.

Altri suggerimenti

Per prima cosa è necessario per calcolare il basso antenato comune sia di A e B . Chiamare questo antenato comune più basso C .

Quindi calcolare la distanza in passi da C per A (CA) e C per B (CB ). Questi valori dovrebbero essere indicizzati in un'altra tabella che determina il rapporto di questi due valori. Ad esempio: 

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

Si potrebbe mantenere i rapporti di base in questa tabella, e aggiungere "ottimo-" per le distanze supplementari su alcuni rapporti, come il nonno, ex .: (0, 3) = bisnonno.

Speriamo che questo vi punto nella giusta direzione. Buona fortuna!

UPDATE: (. Non posso commentare qui sotto il tuo codice, dal momento che non ho la reputazione ancora)

I tuoi aggrandize_relationships funzione è un po 'fuori, credo. È possibile semplificare anteponendo "grande", se l'offset è 1 o superiore, allora prefisso "ottimo-" (offset - 1) volte. La versione potrebbe includere il prefisso "grande grande grande grande" per i parenti molto lontani. (Non sono sicuro se ho il parametro corretto in questa spiegazione, ma spero che si ottiene l'essenza di esso. Inoltre, nessuna idea se il tuo albero genealogico sta che lontano, ma il punto resta valido.)

UPDATE TOO: Siamo spiacenti, quanto sopra non è corretto. Ho letto male il caso di default, e ho pensato che chiama in modo ricorsivo di nuovo la funzione. In mia difesa, non ero familiarità con la notazione "2 ° bisnonno", e sempre usato "trisnonno" me stesso. Codice in poi !!

Questo potrebbe aiutare a The Tree Relationship Calculator è un oggetto che accetta una rappresentazione XML di un albero e calcolerà il rapporto tra qualsiasi due membri al suo interno. Questo articolo descrive come i rapporti sono calcolati, e ciò che termini come cugino di secondo grado, o cugino di primo grado, una volta rimosso, significano. Questo codice include un oggetto di relazioni di calcolo, scritto in JavaScript, così come un'interfaccia web per il rendering e l'interazione con l'albero. Il progetto di esempio è configurato come una pagina ASP classico.

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

Ho risolto questo problema utilizzando lista di adiacenza concetto in java. Uno può avere un nodo per ogni persona e avere i suoi rapporti figlio associati ad esso sul suo nodo stesso. Di seguito è riportato il codice per trovare solo i fratelli e cugini. Tuttavia, è possibile migliorare secondo il vostro requisito. Ho scritto questo codice solo per dimostrazione. 

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

}

Di seguito è riportato il codice principale per aggiungere le persone di famiglia e di trovare relazione tra di loro. 

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

}

Questo potrebbe aiutare te, molta teoria e la realizzazione di query SQL per generare e strutture ad albero di query

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

In particolare, guardare il lista di adiacenza modello che utilizza un albero genealogico come esempio.

Per quanto strano possa sembrare PROLOG sembra essere la cosa che stai cercando. Dato seguente programma ( http://www.pastey.net/117134 colorazione meglio) ad hoc 

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

Si potrebbe chiedere interprete Prolog qualcosa del genere: 

relationship(P1, P2, R).

con le risposte: 


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.

E 'uno strumento potente, se si sa come e quando utilizzarlo. Questo sembra esattamente come un luogo di Prolog. So che non è terribilmente popolare, o facile da incorporare, ma la caratteristica impressionante di wolphram alfa mostrato in uno dei commenti può essere codificato utilizzando nient'altro che costrutti utilizzati in precedenza, e questo è il Prolog 101.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top