graph-theory - sobre - generador de genograma online

Calcular la relación familiar a partir de datos genealógicos

Question

Me gustaría poder calcular la relación familiar entre dos individuos en un árbol genealógico, dado el siguiente esquema de datos (simplificado a partir de mi esquema de datos real, que solo muestra columnas que se aplican directamente a este problema):

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

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

Con esta estructura, ¿cómo se puede calcular la relación entre dos ID individuales (es decir, primo, tío abuelo, etc.)?

Además, como en realidad hay dos relaciones (es decir, AB puede ser sobrino mientras que BA es tío), ¿cómo se puede generar el complemento para el otro (dado tío, y suponiendo que conocemos el género, cómo podemos generar sobrino?). Esta es una pregunta más trivial, la primera es lo que realmente me interesa.

¡Gracias a todos!

Answer 1

A continuación se muestra mi implementación de PHP de mi algoritmo para calcular la relación. Esto se basa en el esquema de datos que describí en la pregunta original. Esto solo encuentra la relación "más cercana", es decir, la ruta más corta entre los dos individuos, no resuelve las relaciones compuestas como la mitad de los hermanos o los primos dobles.

Tenga en cuenta que las funciones de acceso a datos como get_father y get_gender están escritas en el estilo de una capa de abstracción de base de datos que siempre uso. Debería ser bastante sencillo entender lo que está sucediendo, básicamente todas las funciones específicas de dbms como mysql_query se reemplazan con funciones generalizadas como db_query ; no es muy complicado en absoluto, especialmente en los ejemplos de este código, pero no dude en publicar preguntas en los comentarios si no está claro.

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

?>

Como mencioné anteriormente, el algoritmo para determinar el ACV es mucho menos que óptimo. Planeo publicar una pregunta separada para optimizar eso, y otra para abordar el problema del cálculo de relaciones compuestas como los primos dobles.

¡Muchas gracias a todos los que me ayudaron a empujarme en la dirección correcta! Con tus consejos, esto resultó ser mucho más fácil de lo que originalmente pensé.

Answer 2

Esto podría ayudar. La Calculadora de relación de árbol es un objeto que acepta una representación XML de un árbol y calcula la relación de cualquiera de los dos miembros dentro de él. Este artículo describe cómo se calculan las relaciones y qué significan términos como primo segundo o primo una vez que se eliminan. Este código incluye un objeto para calcular relaciones, escrito en JavaScript, así como una interfaz de usuario web para representar e interactuar con el árbol. El proyecto de ejemplo se configura como una página ASP clásica.

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

Answer 3

Esto podría ayudarlo, es una gran cantidad de teoría e implementación de consultas SQL para generar y consultar estructuras de árbol.

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

En particular, observe el modelo de lista de adyacencia que utiliza un árbol familiar como ejemplo.

Answer 4

Por extraño que pueda parecer, PROLOG parece ser lo que estás buscando. Dado el siguiente programa ad-hoc ( http://www.pastey.net/117134 mejor coloración)

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

Podrías preguntarle algo así al intérprete de Prolog:

relationship(P1, P2, R).

con las respuestas:

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 una herramienta poderosa, si sabes cómo y cuándo usarla. Esto parece exactamente como un lugar para Prolog. Sé que no es muy popular o fácil de incrustar, pero la característica impresionante de wolphram alpha que se muestra en uno de los comentarios se puede codificar usando nada más que las construcciones utilizadas anteriormente, y este es Prolog 101.

Answer 5

Primero deberá calcular el antepasado común más bajo de A y B. Llama a este ancestro común más bajo C.

Luego calcule la distancia en pasos de C a A (CA) y de C a B (CB). Estos valores se deben indexar en otra tabla que determine la relación en función de estos dos valores. Por ejemplo:

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

Puede mantener las relaciones básicas en esta tabla y agregar "gran-" para distancias adicionales en ciertas relaciones como abuelo, ej .: (0, 3) = bisabuelo.

Esperemos que esto te apunte en la dirección correcta. ¡La mejor de las suertes!

ACTUALIZACIÓN: (No puedo comentar debajo de tu código, ya que todavía no tengo la reputación).

Su función aggrandize_relationships está un poco apagada, creo. Puede simplificarlo prefijando "grand" si el desplazamiento es 1 o mayor, y luego el prefijo "great-" (offset - 1) veces. Su versión podría incluir el prefijo "grand grand grand grand grand" para parientes muy lejanos. (No estoy seguro de si tengo el parámetro correcto en esta explicación, pero espero que tenga una idea de la misma. Además, no tengo idea si su árbol genealógico se está yendo así). muy atrás, pero el punto sigue siendo válido.)

ACTUALIZAR TAMBIÉN: Lo sentimos, lo anterior es incorrecto. He leído mal el caso predeterminado y pensé que recursivamente llamaba a la función otra vez. En mi defensa, no estaba familiarizado con la notación de "2do bisabuelo", y siempre usé a mí mismo "bisabuelo". Código hacia adelante!

Answer 6

Resolví este problema usando el concepto de lista de adyacencia en java. Uno puede tener un nodo para cada persona y tener sus relaciones secundarias asociadas a él en su propio nodo. A continuación se muestra el código para encontrar solo hermanos y primos. Sin embargo, puede mejorarlo de acuerdo a sus requerimientos. Escribí este código sólo para demostración.

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

}

A continuación se muestra el código principal para agregar personas de la familia y encontrar una relación entre ellos.

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

}