c++ - resueltos - Ciclos en software de árbol genealógico
como hacer un arbol de asteriscos en c++ (18)
Soy el desarrollador de algún software de árbol familiar (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 está procesando (por ejemplo, después de recorrer un ciclo, el programa establece que X no puede ser padre y abuelo de Y).
¿Cómo puedo resolver esos errores sin eliminar todas las afirmaciones de datos?
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 qué datos desea tratar y cuáles están fuera del alcance.
Gráficos de la familia cíclica
Con respecto a los "árboles" familiares (de hecho, son gráficos completos, incluidos los ciclos), hay una bonita anécdota:
Me casé con una viuda que tenía una hija mayor. Mi padre, que nos visitaba a menudo, 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 hijastro de mi esposa. En otras palabras, soy mi propio abuelo.
Las cosas se ponen aún más extrañas cuando se toman en cuenta los surrogates o la "paternidad difusa".
Como lidiar con eso
Definir ciclos como fuera de alcance.
Podría decidir que su software no debería tratar con casos tan raros. Si ocurre tal caso, el usuario debe usar un producto diferente. Esto hace que tratar con los casos más comunes sea mucho más sólido, ya que puede mantener más aserciones y un modelo de datos más simple.
En este caso, agregue algunas buenas funciones 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
Podrías permitir al usuario agregar relaciones manuales. Estas relaciones no son "ciudadanos de primera clase", es decir, el software los toma como están, no los comprueba ni los maneja en el modelo de datos principal.
El usuario puede manejar casos raros a mano. Su modelo de datos seguirá siendo bastante simple y sus afirmaciones sobrevivirán.
Ten cuidado con las relaciones manuales. Existe la tentación de hacerlos completamente configurables y, por lo tanto, crear un modelo de datos completamente 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 denomina "codificación suave" y "El WTF diario" está lleno de ejemplos para eso.
Haga que su modelo de datos sea más flexible, omita aserciones, pruebe 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 fácilmente posible ser tu propio abuelo, por lo que incluso puedes tener ciclos.
En este caso, debe probar extensivamente su software. Tuvo que omitir 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 librerías de verificació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 cruce de forma aleatoria, luego dejar que el 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, donde 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. Trate de encontrar la mayor cantidad posible de invariantes y pruébelos con datos generados aleatoriamente. Los invariantes pueden ser funcionales, por ejemplo:
- un tío sigue siendo 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 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 familiar hasta 10 mil millones de miembros
Al ejecutar las pruebas simuladas, encontrará muchos casos de esquinas extrañas. Arreglarlos tomará mucho tiempo. También perderá muchas optimizaciones, su software se ejecutará mucho más lento. Usted tiene que decidir si vale la pena y si esto está dentro del alcance de su software.
Algunas respuestas han mostrado maneras de mantener las afirmaciones / invariantes, pero esto parece ser un mal uso de las afirmaciones / invariantes. Las afirmaciones son para asegurarse de que algo que debería ser verdad es cierto, y las invariantes son para 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 aserción es inválida. Puede solucionar esta afirmación, pero el error real está en la propia aserción. La aserción debe ser eliminada.
Aquí está el problema con los árboles genealógicos: no son árboles. Son gráficos acíclicos dirigidos o DAGs. Si entiendo correctamente los principios de la biología de la reproducción humana, no habrá ningún ciclo.
Que yo sepa, incluso los cristianos aceptan matrimonios (y, por 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.
Debes centrarte en lo que realmente hace valor para tu software . ¿El tiempo dedicado a hacer que funcione para UN 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 emita un reembolso.
Dejando a un lado las posibles implicaciones legales, ciertamente parece que debe tratar a un ''nodo'' en un árbol familiar como una persona predecesora en lugar de suponer que el nodo puede ser la persona única.
Haga que el nodo del árbol incluya a una persona, así como a los sucesores, y luego puede tener otro nodo más profundo en el árbol que incluye a la misma persona con diferentes sucesores.
Duplicar el padre (o usar 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
En lugar de eliminar todas las afirmaciones, aún debe verificar si una persona es su propio padre u otras situaciones imposibles y presentar un error. Tal vez emita una advertencia si es poco probable que el usuario aún pueda detectar errores comunes de entrada, pero funcionará si todo es correcto.
Almacenaría los datos en un vector con un entero permanente para cada persona y almacenaría los padres y los hijos en objetos personales donde dicho int sea el índice del vector. Esto sería bastante rápido para ir entre generaciones (pero lento para cosas como búsquedas de nombre). Los objetos estarían en orden de cuando fueron creados.
Esta es una de las razones por las que los idiomas como "Ir" no tienen aserciones. Se utilizan para manejar casos en los que probablemente no pensaste, 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( , aléjese durante diez minutos y realmente piense en ello.
En su caso particularmente perturbador, es concebible y espantoso que tal afirmación sea falsa en circunstancias raras pero posibles. Por lo tanto, manipúlala en tu aplicación, aunque solo sea para decir "Este software no fue diseñado para manejar el escenario que presentaste".
Afirmar que tu tatarabuelo, tatarabuelo, ser tu padre como imposible es algo razonable.
Si estuviera trabajando para una empresa de pruebas que fue contratada para probar su software, por supuesto, habría presentado ese escenario. ¿Por qué? Cada "usuario" juvenil e inteligente va a hacer exactamente lo mismo y se deleitará con el "informe de error" resultante.
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 vaya mal allí (tal vez una lista enlazada bidireccional resuelva su problema).
Los datos genealógicos son cíclicos y no encajan en un gráfico acíclico, por lo tanto, si tiene afirmaciones contra los ciclos, debe 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 de abuelo se muestra normalmente, pero el nodo padre se representa como un nodo "fantasma" que tiene una etiqueta simple como ("ver abuelo" ) y apunta al abuelo.
Para realizar cálculos, es posible que necesite mejorar su lógica para manejar gráficos cíclicos de modo que un nodo no sea visitado más de una vez si hay un ciclo.
Odio comentar sobre una situación tan complicada, pero la forma más fácil de no reagrupar a todos tus invariantes es crear un vértice fantasma en tu gráfica que actúe como un proxy para el padre incestuoso.
Otra respuesta seria falsa para una pregunta tonta:
La verdadera respuesta es usar una estructura de datos apropiada. La genealogía humana no puede expresarse completamente usando un árbol puro sin ciclos. Deberías usar algún tipo de gráfica. Además, hable con un antropólogo antes de seguir adelante con esto, porque hay muchos otros lugares donde se pueden cometer errores similares al tratar de modelar la genealogía, incluso en el caso más simple del "matrimonio monógamo patriarcal occidental".
Incluso si queremos ignorar las relaciones tabúes locales, como se explica aquí, hay muchas formas perfectamente legales y completamente inesperadas de introducir ciclos en un árbol familiar.
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 que 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 se legitima a los niños con el propósito de la herencia, puede ser alterada por alguna excepción en algún lugar del mundo o la historia.
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 familiar en su cartera, y hemos estado luchando con problemas similares.
El problema, en nuestro caso, y supongo que su caso también, proviene del formato GEDCOM que es extremadamente crítico sobre lo que debería ser una familia. Sin embargo, este formato contiene algunas ideas erróneas acerca de cómo se ve realmente un árbol familiar.
GEDCOM tiene muchos problemas, como la incompatibilidad con las relaciones entre personas del mismo sexo, incesto, etc ... Lo que en la vida real ocurre con más frecuencia de lo que imaginas (especialmente cuando se remonta al tiempo hasta el 1700-1800).
Hemos modelado nuestro árbol genealógico de acuerdo con lo que sucede en el mundo real: eventos (por ejemplo, nacimientos, bodas, compromisos, uniones, muertes, adopciones, etc.). No imponemos ninguna restricción a estos, a excepción de los lógicamente imposibles (por ejemplo, uno no puede ser el propio padre, las relaciones necesitan dos personas, etc.)
La falta de validaciones nos da una solución más "real", más simple y más flexible.
En cuanto a este caso específico, sugeriría eliminar las aserciones, ya que no son universales.
Para los problemas de visualización (que surgirán) sugeriría dibujar el mismo nodo tantas veces como sea necesario, insinuando la duplicación al encender todas las copias al seleccionar una de ellas.
Por lo tanto, he hecho un trabajo en el software de árbol de familia. Creo que el problema que estás tratando de resolver es que necesitas poder caminar el árbol sin entrar en infinitos bucles; 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 grafo 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 superposición, tendrías más ancestros en 1000 AD que personas con vida. Por lo tanto, tiene que haber superposición.
Sin embargo, también tiende a obtener ciclos que no son válidos, solo datos erróneos. Si estás atravesando el árbol, entonces los ciclos deben ser tratados. Puede hacer esto en cada algoritmo individual, o en carga. Lo hice en carga.
Encontrar ciclos verdaderos en un árbol se puede hacer de varias maneras. La forma incorrecta es marcar cada antepasado de un individuo determinado, y cuando se atraviesa, si la persona que va a pasar al siguiente ya está marcada, corte el enlace. Esto cortará relaciones potencialmente precisas. La forma correcta de hacerlo es comenzar desde cada individuo y marcar a cada antepasado con el camino hacia ese individuo. Si la nueva ruta contiene la ruta actual como una ruta secundaria, entonces es un ciclo y se debe romper. Puede almacenar rutas como vector <bool> (MFMF, MFFFMF, etc.) lo que hace que la comparación y el almacenamiento sean muy rápidos.
Hay otras formas de detectar ciclos, como enviar dos iteradores y ver si alguna vez chocan con la prueba de subconjunto, pero terminé usando el método de almacenamiento local.
Además, tenga en cuenta que no es necesario que corte realmente el enlace, simplemente puede cambiarlo de un enlace normal a uno débil, al que no siguen algunos de sus algoritmos. También querrá 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 la fecha de nacimiento, pero a menudo no puede descubrir nada porque faltan muchos datos.
Relaja tus afirmaciones.
No cambiando las reglas, que en su mayoría son muy útiles para que el 99.9% de sus clientes detecten errores al ingresar sus datos.
En su lugar, cámbielo de un error "no se puede agregar relación" a una advertencia con un "agregar de todos modos".
Su árbol genealógico debe utilizar relaciones dirigidas. De esta manera no tendrás un ciclo.
Supongo que tiene algún valor que identifica de manera única a una persona en la que puede basar sus cheques.
Esta es una pregunta difícil. Suponiendo que desea mantener la estructura de un árbol, sugiero esto:
Supongamos esto: A tiene hijos con su propia hija.
A suma al programa como A y como B Una vez en el papel de padre, llamémosle novio.
Agregue una función is_same_for_out() que indica a la parte de generación de salida de su programa que todos los enlaces que van a B internamente deben ir a A en la presentación de datos.
Esto supondrá un trabajo adicional para el usuario, pero creo que sería relativamente fácil de implementar y mantener.
A partir de eso, podría trabajar en la sincronización de código A y B para evitar inconsistencias.
Esta solución seguramente no es perfecta, pero es un primer enfoque.