Pregunta 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 programa indica que X no puede ser padre ni abuelo de Y).

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


1594
2018-05-28 18:39


origen


Respuestas:


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 su caso también, proviene de la GEDCOM formato 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.


727
2018-06-01 08:25



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


564
2018-05-28 19:20



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.


224
2018-06-01 09:58



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:

Asume esto: A tiene hijos con su propia hija.

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

Agrega un is_same_for_out() función que le dice a la salida que genera parte de su programa que todos los enlaces van a B internamente debería ir a A en la presentación de 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ías trabajar en la sincronización de códigos A y B para evitar inconsistencias

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


115
2018-05-28 18:50



Deberías enfocarte en lo que realmente da valor a tu 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 alcance de su software y le envíe un reembolso.


84
2018-06-01 08:51



Deberías haber configurado el Atreides familia (ya sea moderna, Duna, o antiguo, Edipo Rey) como un caso de prueba. No encuentra errores al usar datos desinfectados como caso de prueba.


79
2018-06-01 16:10



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 solo lo improbable. Hacer esto último es lo que da a las afirmaciones una mala reputación. Cada vez que escribes assert(, alejarse por diez minutos y De Verdad Piénsalo.

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é? Todo 'usuario' juvenil pero inteligente va a hacer exactamente lo mismo y saborear en el 'informe de error' resultante.


59
2018-06-01 06:10



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.


41
2018-05-28 18:55



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 una Gráfico Acíclico Dirigido(TROZO DE CUERO). 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 <bool> (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.


37
2018-06-01 18:39