Ciclos en software de árbol genealógico

Soy el desarrollador de algún software de árbol genealógico (escrito en C ++ y Qt). No tuve problemas hasta que uno de mis clientes me envió un informe de error. El problema es que el cliente tiene dos hijos con su propia hija y, como resultado, no puede usar mi software debido a errores.

Esos errores son el resultado de mis diversas afirmaciones e invariantes sobre el gráfico familiar que se procesa (por ejemplo, después de recorrer un ciclo, el progtwig indica que X no puede ser padre ni abuelo de Y).

¿Cómo puedo resolver esos errores sin eliminar todas las aserciones de datos?

Parece que usted (y / o su compañía) tienen un malentendido fundamental de lo que se supone que es un árbol genealógico.

Permítanme aclarar, también trabajo para una empresa que tiene (como uno de sus productos) un árbol genealógico en su cartera, y hemos estado luchando con problemas similares.

El problema, en nuestro caso, y supongo que también su caso, proviene del formato GEDCOM que es extremadamente dogmático sobre lo que debería ser una familia. Sin embargo, este formato contiene algunos conceptos erróneos sobre cómo es realmente un árbol genealógico.

GEDCOM tiene muchos problemas, como la incompatibilidad con las relaciones del mismo sexo, el incesto, etc., que en la vida real ocurre con más frecuencia de lo que imagina (especialmente al retroceder en el tiempo hasta el 1700-1800).

Hemos modelado nuestro árbol genealógico para lo que sucede en el mundo real: Eventos (por ejemplo, nacimientos, bodas, compromiso, uniones, muertes, adopciones, etc.). No ponemos ninguna restricción sobre estos, excepto los lógicamente imposibles (por ejemplo, uno no puede ser uno de los padres, las relaciones necesitan dos personas, etc.)

La falta de validaciones nos brinda una solución más “real”, más simple y más flexible.

En cuanto a este caso específico, sugiero eliminar las afirmaciones ya que no son universales.

Para mostrar los problemas (que surgirán), sugeriría dibujar el mismo nodo tantas veces como sea necesario, haciendo alusión a la duplicación iluminando todas las copias al seleccionar una de ellas.

Relaje sus afirmaciones.

No cambiando las reglas, que probablemente sean muy útiles para el 99,9% de los clientes al detectar errores al ingresar sus datos.

En su lugar, cámbialo de un error “no se puede agregar relación” a una advertencia con un “agregar de todos modos”.

Aquí está el problema con los árboles genealógicos: no son árboles. Son gráficos acíclicos dirigidos o DAG. Si entiendo correctamente los principios de la biología de la reproducción humana, no habrá ningún ciclo.

Hasta donde yo sé, incluso los cristianos aceptan matrimonios (y por lo tanto hijos) entre primos, lo que convertirá el árbol genealógico en un DAG familiar.

La moraleja de la historia es: elegir las estructuras de datos correctas.

Supongo que tiene algún valor que identifica de forma única a una persona en la que puede basar sus cheques.

Esto es complicado. Suponiendo que quiera mantener la estructura en un árbol, sugiero esto:

Asum esto: A tiene hijos con su propia hija.

A agrega al progtwig como A y como B Una vez en el papel de padre, vamos a llamarlo novio.

Agregue una función is_same_for_out() que le indique a la parte generadora de resultados de su progtwig que todos los enlaces que van a B internamente deberían dirigirse a A en la presentación de los datos.

Esto hará un poco de trabajo adicional para el usuario, pero supongo que sería relativamente fácil de implementar y mantener.

A partir de eso, podría trabajar en la sincronización de códigos A y B para evitar incoherencias.

Esta solución seguramente no es perfecta, pero es un primer acercamiento.

Debería concentrarse en lo que realmente le da valor a su software . ¿El tiempo dedicado a hacer que funcione para UN solo consumidor vale el precio de la licencia? Probablemente no.

Le aconsejo que se disculpe con este cliente, le diga que su situación está fuera del scope de su software y le envíe un reembolso.

Deberías haber configurado a la familia Atreides (ya sea moderna, Dune o antigua, Edipo Rex ) como un caso de prueba. No encuentra errores al usar datos desinfectados como caso de prueba.

Esta es una de las razones por las que los lenguajes como “Ir” no tienen aserciones. Se usan para manejar casos en los que probablemente no pensó, con demasiada frecuencia. Solo debes afirmar lo imposible, no simplemente lo improbable . Hacer esto último es lo que da a las afirmaciones una mala reputación. Cada vez que escriba assert( , alejarse durante diez minutos y realmente pensar en ello.

En su caso particularmente inquietante, es concebible y atroz que tal afirmación sea falsa en circunstancias raras pero posibles. Por lo tanto, trátelo en tu aplicación, solo para decir “Este software no fue diseñado para manejar el escenario que presentaste”.

Afirmar que tu tatarabuelo, tu tatarabuelo es tu padre como imposible, es algo razonable de hacer.

Si estuviera trabajando para una empresa de pruebas que fue contratada para probar su software, por supuesto que habría presentado ese escenario. ¿Por qué? Cada ‘usuario’ juvenil pero inteligente hará exactamente lo mismo y se deleitará en el ‘informe de error’ resultante.

Odio comentar sobre una situación tan jodida, pero la forma más fácil de no rejigger todas tus invariantes es crear un vértice fantasma en tu gráfico que actúe como un proxy para el padre incestuoso.

Por lo tanto, he hecho algo de trabajo en el software de árbol genealógico. Creo que el problema que estás tratando de resolver es que necesitas poder caminar por el árbol sin tener que entrar en ciclos infinitos; en otras palabras, el árbol debe ser acíclico.

Sin embargo, parece que estás afirmando que solo hay un camino entre una persona y uno de sus antepasados. Eso garantizará que no haya ciclos, pero es demasiado estricto. Biológicamente hablando, la descendencia es un gráfico acíclico dirigido (DAG). El caso que tienes es ciertamente un caso degenerado, pero ese tipo de cosas sucede todo el tiempo en árboles más grandes.

Por ejemplo, si observas los 2 ^ n ancestros que tienes en la generación n, si no hubo solapamiento, entonces tendrías más antepasados ​​en 1000 d. C. que personas vivas. Entonces, tiene que haber superposición.

Sin embargo, también tiende a obtener ciclos que no son válidos, solo datos incorrectos. Si estás atravesando el árbol, entonces se deben tratar los ciclos. Puedes hacer esto en cada algoritmo individual, o en carga. Lo hice en la carga.

Encontrar verdaderos ciclos en un árbol se puede hacer de varias maneras. La forma incorrecta es marcar a cada antepasado de un individuo dado, y al atravesarlo, si la persona a la que va a pasar ahora ya está marcada, entonces corte el enlace. Esto cortará las relaciones potencialmente precisas. La forma correcta de hacerlo es comenzar por cada individuo y marcar a cada antepasado con el camino hacia ese individuo. Si la nueva ruta contiene la ruta actual como un subpaso, entonces es un ciclo y debe romperse. Puede almacenar rutas como vector (MFMF, MFFFMF, etc.) lo que hace que la comparación y el almacenamiento sean muy rápidos.

Hay algunas otras formas de detectar ciclos, como enviar dos iteradores y ver si alguna vez colisionan con la prueba de subconjunto, pero terminé usando el método de almacenamiento local.

También tenga en cuenta que no necesita cortar realmente el enlace, simplemente puede cambiarlo de un enlace normal a uno “débil”, que no es seguido por algunos de sus algoritmos. También deberá tener cuidado al elegir qué enlace marcar como débil; a veces puede averiguar dónde debe romperse el ciclo mirando la información de fecha de nacimiento, pero a menudo no puede descubrir nada porque faltan demasiados datos.

Otra respuesta seria falsa para una pregunta tonta:

La verdadera respuesta es usar una estructura de datos apropiada. La genealogía humana no se puede express completamente usando un árbol puro sin ciclos. Deberías usar algún tipo de gráfico. Además, hable con un antropólogo antes de ir más allá con esto, porque hay muchos otros lugares donde se podrían cometer errores similares al tratar de modelar la genealogía, incluso en el caso más simple de “matrimonio monógamo patriarcal occidental”.

Incluso si queremos ignorar las relaciones tabú a nivel local como se discutió aquí, hay muchas formas perfectamente legales e inesperadas de introducir ciclos en un árbol genealógico.

Por ejemplo: http://en.wikipedia.org/wiki/Cousin_marriage

Básicamente, el matrimonio primo no solo es común y esperado, es la razón por la cual los humanos han pasado de miles de pequeños grupos familiares a una población mundial de 6 mil millones. No puede funcionar de otra manera.

Realmente hay muy pocos universales cuando se trata de genealogía, familia y linaje. Casi cualquier suposición estricta acerca de las normas que sugieren quién puede ser una tía, o quién puede casarse con quién, o cómo los niños son legitimados con el propósito de heredar, puede verse alterada por alguna excepción en algún lugar del mundo o de la historia.

Dejando a un lado las posibles implicaciones legales, ciertamente parece que necesita tratar un ‘nodo’ en un árbol genealógico como una persona predecesora en lugar de asumir que el nodo puede ser la única persona.

Haga que el nodo árbol incluya a una persona, así como a los sucesores, y luego puede tener otro nodo más profundo en el árbol que incluya a la misma persona con diferentes sucesores.

Algunas respuestas han mostrado formas de mantener las aserciones / invariantes, pero esto parece ser un mal uso de aserciones / invariantes. Las afirmaciones son para asegurarse de que algo que debería ser cierto es verdadero, y las invariantes deben asegurarse de que algo que no debería cambiar no cambie.

Lo que estás afirmando aquí es que las relaciones incestuosas no existen. Claramente existen, por lo que su afirmación es inválida. Puede evitar esta afirmación, pero el verdadero error está en la afirmación misma. La afirmación debería ser eliminada.

Su árbol genealógico debe usar relaciones dirigidas. De esta forma no tendrás un ciclo.

Los datos genealógicos son cíclicos y no se ajustan a un gráfico acíclico, por lo que si tienes afirmaciones contra ciclos, debes eliminarlos.

La forma de manejar esto en una vista sin crear una vista personalizada es tratar al padre cíclico como un padre “fantasma”. En otras palabras, cuando una persona es tanto padre como abuelo de la misma persona, entonces el nodo abuelo se muestra normalmente, pero el nodo padre se representa como un nodo “fantasma” que tiene una etiqueta simple como (“ver abuelo” ) y señala al abuelo.

Para hacer cálculos, puede que necesite mejorar su lógica para manejar gráficos cíclicos de manera que un nodo no se visite más de una vez si hay un ciclo.

Lo más importante es avoid creating a problem , por lo que creo que debes usar una relación directa para evitar tener un ciclo.

Como dijo @markmywords, #include “fritzl.h”.

Finalmente, tengo que decir que recheck your data structure a recheck your data structure . Tal vez algo va mal allí (tal vez una lista vinculada bidireccional resuelva su problema).

Las afirmaciones no sobreviven a la realidad

Por lo general, las afirmaciones no sobreviven al contacto con datos del mundo real. Es parte del proceso de ingeniería de software decidir, con qué datos desea tratar y cuáles están fuera del scope.

Gráficos familiares cíclicos

En cuanto a los “árboles” familiares (de hecho son gráficos completos, incluidos los ciclos), hay una agradable anécdota:

Me casé con una viuda que tenía una hija adulta. Mi padre, que a menudo nos visitaba, se enamoró de mi hijastra y se casó con ella. Como resultado, mi padre se convirtió en mi hijo y mi hija se convirtió en mi madre. Algún tiempo después, le di a mi esposa un hijo, que era el hermano de mi padre y mi tío. La esposa de mi padre (que también es mi hija y mi madre) tiene un hijo. Como resultado, tengo un hermano y un nieto en la misma persona. Mi esposa ahora es mi abuela, porque ella es la madre de mi madre. Así que soy el esposo de mi esposa y, al mismo tiempo, el nieto de mi esposa. En otras palabras, soy mi propio abuelo.

Las cosas se ponen aún más extrañas, cuando tomas en cuenta los sustitutos o la “paternidad difusa”.

Cómo lidiar con eso

Definir ciclos como fuera de scope

Podría decidir que su software no debería tratar casos tan extraños. Si tal caso ocurre, el usuario debería usar un producto diferente. Esto hace que ocuparse de los casos más comunes sea mucho más sólido, ya que puede mantener más afirmaciones y un modelo de datos más simple.

En este caso, agregue algunas buenas características de importación y exportación a su software, para que el usuario pueda migrar fácilmente a un producto diferente cuando sea necesario.

Permitir relaciones manuales

Puede permitir que el usuario agregue relaciones manuales. Estas relaciones no son “ciudadanos de primera clase”, es decir, el software las toma tal como están, no las verifica y no las maneja en el modelo de datos principal.

El usuario puede manejar casos extraños a mano. Su modelo de datos seguirá siendo bastante simple y sus afirmaciones sobrevivirán.

Tenga cuidado con las relaciones manuales. Existe la tentación de hacerlos completamente configurables y, por lo tanto, crear un modelo de datos totalmente configurable. Esto no funcionará: su software no se escalará, obtendrá errores extraños y finalmente la interfaz de usuario quedará inutilizable. Este antipatrón se llama “encoding suave” y “La WTF diaria” está llena de ejemplos para eso.

Haga que su modelo de datos sea más flexible, saltee las afirmaciones, pruebe las invariantes

El último recurso sería hacer que su modelo de datos sea más flexible. Tendría que omitir casi todas las afirmaciones y basar su modelo de datos en un gráfico completo. Como muestra el ejemplo anterior, es muy posible que sea su propio abuelo, por lo que incluso puede tener ciclos.

En este caso, debe probar extensivamente su software. Tuviste que saltear casi todas las afirmaciones, por lo que hay una buena posibilidad de errores adicionales.

Use un generador de datos de prueba para verificar casos de prueba inusuales. Hay bibliotecas de comprobación rápida para Haskell , Erlang o C. Para Java / Scala hay ScalaCheck y Nyaya . Una idea de prueba sería simular una población aleatoria, dejar que se mezcle al azar, luego dejar que su software primero importe y luego exporte el resultado. La expectativa sería que todas las conexiones en la salida también están en la entrada y viceversa.

Un caso en el que una propiedad permanece igual se llama invariante. En este caso, el invariante es el conjunto de “relaciones románticas” entre los individuos en la población simulada. Intente encontrar tantas invariantes como sea posible y pruébelas con datos generados aleatoriamente. Las invariantes pueden ser funcionales, por ejemplo:

  • un tío se queda tío, incluso cuando agregas más “relaciones románticas”
  • cada niño tiene un padre
  • una población con dos generaciones tiene al menos un abuelo

O pueden ser técnicos:

  • Su software no se bloqueará en un gráfico de hasta 10 mil millones de miembros (sin importar cuántas interconexiones)
  • Su software se escala con O (número de nodos) y O (número de bordes ^ 2)
  • Su software puede guardar y volver a cargar cada gráfico de familia hasta 10 mil millones de miembros

Al ejecutar las pruebas simuladas, encontrará muchos casos extraños en las esquinas. Repararlos llevará mucho tiempo. Además, perderá muchas optimizaciones, su software funcionará mucho más lento. Debe decidir si vale la pena y si esto está dentro del scope de su software.

En lugar de eliminar todas las afirmaciones, debe verificar las cosas como que una persona es su padre u otras situaciones imposibles y presentar un error. Tal vez emita una advertencia si es poco probable, de modo que el usuario aún pueda detectar errores de entrada comunes, pero funcionará si todo es correcto.

Yo almacenaba los datos en un vector con un entero permanente para cada persona y almacenaba los padres y los niños en objetos personales donde dicho int era el índice del vector. Esto sería bastante rápido para pasar de una generación a otra (pero lenta para cosas como búsquedas de nombres). Los objetos estarían en orden de cuando fueron creados.

Duplique el padre (o use el enlace simbólico / referencia).

Por ejemplo, si está utilizando una base de datos jerárquica:

 $ #each person node has two nodes representing its parents. $ mkdir Family $ mkdir Family/Son $ mkdir Family/Son/Daughter $ mkdir Family/Son/Father $ mkdir Family/Son/Daughter/Father $ ln -s Family/Son/Daughter/Father Family/Son/Father $ mkdir Family/Son/Daughter/Wife $ tree Family Family └── Son ├── Daughter │ ├── Father │ └── Wife └── Father -> Family/Son/Daughter/Father 4 directories, 1 file 
Intereting Posts