Je suis le développeur d'un logiciel d'arbre généalogique (écrit en C ++ et Qt). Je n'ai eu aucun problème jusqu'à ce qu'un de mes clients m'envoie un rapport de bogue. Le problème est que le client a deux enfants avec leur propre fille et, par conséquent, il ne peut pas utiliser mon logiciel en raison d'erreurs.

Ces erreurs sont le résultat de mes diverses affirmations et invariants concernant le graphique de famille en cours de traitement (par exemple, après avoir parcouru un cycle, le programme déclare que X ne peut pas être à la fois père et grand-père de Y).

Comment puis-je résoudre ces erreurs sans supprimer toutes les assertions de données?

Il semble que vous (et / ou votre entreprise) ayez une incompréhension fondamentale de ce qu'est un arbre généalogique.

Permettez-moi de clarifier, je travaille également pour une entreprise qui a (comme l'un de ses produits) un arbre généalogique dans son portefeuille, et nous avons eu des problèmes similaires.

Le problème, dans notre cas, et je suppose que votre cas aussi, vient du format GEDCOM qui est extrêmement avisé sur ce que devrait être une famille. Cependant, ce format contient de graves idées fausses sur l'apparence réelle d'un arbre généalogique.

GEDCOM a de nombreux problèmes, tels que l'incompatibilité avec les relations homosexuelles, l'inceste, etc ... Ce qui se produit dans la vie réelle plus souvent que vous ne l'imaginez (surtout lorsque vous remontez le temps vers le 1700-1800).

Nous avons modelé notre arbre généalogique sur ce qui se passe dans le monde réel: événements (par exemple, naissances, mariages, fiançailles, unions, décès, adoptions, etc.). Nous ne leur imposons aucune restriction, sauf celles logiquement impossibles (par exemple, on ne peut pas être son propre parent, les relations ont besoin de deux personnes, etc.)

L'absence de validations nous donne une solution plus "réelle", plus simple et plus flexible.

Quant à ce cas spécifique, je suggère de supprimer les affirmations car elles ne sont pas universelles.

Pour afficher les problèmes (qui se poseront), je suggère de dessiner le même nœud autant de fois que nécessaire, en faisant allusion à la duplication en allumant toutes les copies lors de la sélection de l'un d'entre eux.

Détendez vos affirmations.

Pas en modifiant les règles, qui sont généralement très utiles à 99,9% de vos clients pour détecter les erreurs lors de la saisie de leurs données.

Au lieu de cela, remplacez-le par une erreur «impossible d'ajouter une relation» par un avertissement avec un «ajouter quand même».

Voici le problème avec les arbres généalogiques: ce ne sont pas des arbres. Ce sont des graphes acycliques ou DAG dirigés. Si je comprends bien les principes de la biologie de la reproduction humaine, il n'y aura pas de cycles.

Pour autant que je sache, même les chrétiens acceptent les mariages (et donc les enfants) entre cousins, ce qui transformera l'arbre généalogique en un DAG familial.

La morale de l'histoire est: choisissez les bonnes structures de données.

Je suppose que vous avez une valeur qui identifie de manière unique une personne sur laquelle vous pouvez baser vos chèques.

Ceci est délicat. En supposant que vous souhaitiez conserver la structure sous forme d'arbre, je suggère ceci:

Supposons ceci: Aa des enfants avec sa propre fille.

As'ajoute au programme au fur Aet à mesureB . Une fois dans le rôle de père, appelons-le petit ami.

Ajoutez une is_same_for_out()fonction qui indique à la partie génératrice de sortie de votre programme que tous les liens qui vont en Binterne devraient allerA lors de la présentation des données.

Cela fera un travail supplémentaire pour l'utilisateur, mais je suppose que l'informatique serait relativement facile à mettre en œuvre et à maintenir.

À partir de cela, vous pouvez travailler sur la synchronisation du code Aet Béviter les incohérences.

Cette solution n'est sûrement pas parfaite, mais c'est une première approche.

Vous devez vous concentrer sur ce qui fait vraiment la valeur de votre logiciel . Le temps consacré à le faire fonctionner pour UN consommateur vaut-il le prix de la licence? Probablement pas.

Je vous conseille de vous excuser auprès de ce client, lui dire que sa situation est hors de portée de votre logiciel et lui rembourser.

Vous devriez avoir configuré la famille Atreides (moderne, Dune ou ancienne, Oedipus Rex ) comme cas de test. Vous ne trouvez pas de bogues en utilisant des données filtrées comme cas de test.

C'est l'une des raisons pour lesquelles des langues comme "Go" n'ont pas d'assertions. Ils sont utilisés pour gérer des cas auxquels vous n'avez probablement pas pensé, trop souvent. Vous ne devez affirmer que l'impossible, pas simplement l'improbable . Faire ce dernier est ce qui donne aux assertions une mauvaise réputation. Chaque fois que vous tapez assert(, éloignez-vous pendant dix minutes et vraiment réfléchissez-y .

Dans votre cas particulièrement inquiétant, il est à la fois concevable et épouvantable qu'une telle affirmation soit fausse dans des circonstances rares mais possibles. Par conséquent, gérez-le dans votre application, ne serait-ce que pour dire "Ce logiciel n'a pas été conçu pour gérer le scénario que vous avez présenté".

Affirmer que votre arrière-arrière-arrière-grand-père est votre père est impossible est une chose raisonnable à faire.

Si je travaillais pour une société de test embauchée pour tester votre logiciel, j'aurais bien sûr présenté ce scénario. Pourquoi? Chaque «utilisateur» juvénile mais intelligent va faire exactement la même chose et savourer le «rapport de bogue» qui en résulte.

Je déteste commenter une situation aussi foutue, mais le moyen le plus simple de ne pas relancer tous vos invariants est de créer un sommet fantôme dans votre graphique qui agit comme un proxy pour le père incestueux.

J'ai donc travaillé sur un logiciel d'arbre généalogique. Je pense que le problème que vous essayez de résoudre est que vous devez être en mesure de marcher sur l'arbre sans faire de boucles infinies - en d'autres termes, l'arbre doit être acyclique.

Cependant, il semble que vous affirmiez qu'il n'y a qu'un seul chemin entre une personne et l'un de ses ancêtres. Cela garantira qu'il n'y a pas de cycles, mais c'est trop strict. Biologiquement parlant, la descendance est un graphe acyclique dirigé (DAG). Le cas que vous avez est certainement un cas dégénéré, mais ce genre de chose se produit tout le temps sur des arbres plus gros.

Par exemple, si vous regardez les 2 ^ n ancêtres que vous avez à la génération n, s'il n'y avait pas de chevauchement, alors vous auriez plus d'ancêtres en 1000 AD qu'il n'y avait de personnes vivantes. Donc, il doit y avoir un chevauchement.

Cependant, vous avez également tendance à obtenir des cycles non valides, juste de mauvaises données. Si vous traversez l'arbre, les cycles doivent être traités. Vous pouvez le faire dans chaque algorithme individuel ou en charge. Je l'ai fait en charge.

Trouver de vrais cycles dans un arbre peut se faire de plusieurs manières. La mauvaise façon est de marquer chaque ancêtre d'un individu donné, et lorsque vous traversez, si la personne que vous allez passer à l'étape suivante est déjà marquée, coupez le lien. Cela rompra les relations potentiellement précises. La façon correcte de le faire est de partir de chaque individu et de marquer chaque ancêtre avec le chemin d'accès à cet individu. Si le nouveau chemin contient le chemin actuel en tant que sous-chemin, alors c'est un cycle et doit être interrompu. Vous pouvez stocker des chemins en tant que vecteur <bool> (MFMF, MFFFMF, etc.), ce qui rend la comparaison et le stockage très rapides.

Il existe plusieurs autres façons de détecter les cycles, comme l'envoi de deux itérateurs et la vérification de leur collision avec le test de sous-ensemble, mais j'ai fini par utiliser la méthode de stockage local.

Notez également que vous n'avez pas besoin de couper réellement le lien, vous pouvez simplement le changer d'un lien normal en un lien «faible», qui n'est pas suivi par certains de vos algorithmes. Vous voudrez également faire attention lors du choix du lien à marquer comme faible; Parfois, vous pouvez déterminer où le cycle doit être rompu en consultant les informations de date de naissance, mais souvent vous ne pouvez rien comprendre car il manque tellement de données.

Une autre réponse sérieuse simulée pour une question stupide:

La vraie réponse est d'utiliser une structure de données appropriée. La généalogie humaine ne peut pas être entièrement exprimée en utilisant un arbre pur sans cycles. Vous devez utiliser une sorte de graphique. Parlez également à un anthropologue avant d'aller plus loin, car il existe de nombreux autres endroits où des erreurs similaires pourraient être commises en essayant de modéliser la généalogie, même dans le cas le plus simple du «mariage monogame patriarcal occidental».

Même si nous voulons ignorer les relations taboues locales comme nous le verrons ici, il existe de nombreuses façons parfaitement légales et complètement inattendues d'introduire des cycles dans un arbre généalogique.

Par exemple: http://en.wikipedia.org/wiki/Cousin_marriage

Fondamentalement, le mariage entre cousins ​​n'est pas seulement courant et attendu, c'est la raison pour laquelle les humains sont passés de milliers de petits groupes familiaux à une population mondiale de 6 milliards d'habitants. Cela ne peut pas fonctionner autrement.

Il y a vraiment très peu d'universaux en ce qui concerne la généalogie, la famille et la lignée. Presque toute hypothèse stricte sur les normes suggérant qui peut être une tante, ou qui peut épouser qui, ou comment les enfants sont légitimés à des fins d'héritage, peut être bouleversée par une exception quelque part dans le monde ou dans l'histoire.

Hormis les implications juridiques potentielles, il semble certainement que vous devez traiter un `` nœud '' sur un arbre généalogique comme une personne prédécesseur plutôt que de supposer que le nœud peut être la seule et unique personne.

Demandez au nœud d'arbre d'inclure une personne ainsi que les successeurs - et ensuite vous pouvez avoir un autre nœud plus en bas de l'arbre qui comprend la même personne avec différents successeurs.

Quelques réponses ont montré des moyens de conserver les assertions / invariants, mais cela semble être une mauvaise utilisation des assertions / invariants. Les assertions visent à s'assurer que quelque chose qui devrait être vrai est vrai, et les invariants doivent s'assurer que quelque chose qui ne devrait pas changer ne change pas.

Ce que vous affirmez ici, c'est que les relations incestueuses n'existent pas. De toute évidence , ils ne existent, de sorte que votre affirmation est invalide. Vous pouvez contourner cette assertion, mais le vrai bogue se trouve dans l'assertion elle-même. L'affirmation doit être supprimée.

Votre arbre généalogique doit utiliser des relations dirigées. De cette façon, vous n'aurez pas de cycle.

Les données généalogiques sont cycliques et ne rentrent pas dans un graphique acyclique, donc si vous avez des affirmations contre les cycles, vous devez les supprimer.

La façon de gérer cela dans une vue sans créer de vue personnalisée consiste à traiter le parent cyclique comme un parent "fantôme". En d'autres termes, lorsqu'une personne est à la fois un père et un grand-père pour la même personne, le nœud de grand-père est affiché normalement, mais le nœud de père est rendu comme un nœud "fantôme" qui a une étiquette simple comme ("voir grand-père" ) et désigne le grand-père.

Afin de faire des calculs, vous devrez peut-être améliorer votre logique pour gérer les graphiques cycliques afin qu'un nœud ne soit pas visité plus d'une fois s'il y a un cycle.

La chose la plus importante est de avoid creating a problem, donc je crois que vous devez utiliser une relation directe pour éviter d'avoir un cycle.

Comme l'a dit @markmywords, #include "fritzl.h".

Enfin je dois dire recheck your data structure. Peut-être que quelque chose ne va pas là-bas (peut-être qu'une liste chaînée bidirectionnelle résout votre problème).

Les affirmations ne survivent pas à la réalité

Habituellement, les assertions ne survivent pas au contact avec des données réelles. Cela fait partie du processus de génie logiciel de décider, avec quelles données vous voulez traiter et lesquelles sont hors de portée.

Graphes de famille cycliques

Concernant les "arbres" de famille (en fait ce sont des graphiques à part entière, y compris des cycles), il y a une belle anecdote:

J'ai épousé une veuve qui avait une fille adulte. Mon père, qui nous rendait souvent visite, est tombé amoureux de ma belle-fille et l'a épousée. En conséquence, mon père est devenu mon fils et ma fille est devenue ma mère. Quelque temps plus tard, j'ai donné à ma femme un fils, qui était le frère de mon père et mon oncle. La femme de mon père (qui est aussi ma fille et ma mère) a eu un fils. En conséquence, j'ai eu un frère et un petit-fils dans la même personne. Ma femme est maintenant ma grand-mère, car elle est la mère de ma mère. Je suis donc le mari de ma femme et en même temps le beau-petit-fils de ma femme. En d'autres termes, je suis mon propre grand-père.

Les choses deviennent encore plus étranges lorsque l'on tient compte des substituts ou de la "paternité floue".

Comment y faire face

Définir les cycles comme hors champ

Vous pourriez décider que votre logiciel ne devrait pas traiter de tels cas rares. Si un tel cas se produit, l'utilisateur doit utiliser un produit différent. Cela rend le traitement des cas les plus courants beaucoup plus robuste, car vous pouvez conserver plus d'assertions et un modèle de données plus simple.

Dans ce cas, ajoutez de bonnes fonctionnalités d'importation et d'exportation à votre logiciel, afin que l'utilisateur puisse facilement migrer vers un autre produit si nécessaire.

Autoriser les relations manuelles

Vous pouvez autoriser l'utilisateur à ajouter des relations manuelles. Ces relations ne sont pas des «citoyens de première classe», c'est-à-dire que le logiciel les prend telles quelles, ne les vérifie pas et ne les gère pas dans le modèle de données principal.

L'utilisateur peut alors gérer les rares cas à la main. Votre modèle de données restera assez simple et vos affirmations survivront.

Soyez prudent avec les relations manuelles. Il y a une tentation de les rendre complètement configurables et donc de créer un modèle de données entièrement configurable. Cela ne fonctionnera pas: votre logiciel ne sera pas redimensionné, vous obtiendrez d'étranges bugs et enfin l'interface utilisateur deviendra inutilisable. Cet anti-modèle est appelé "codage logiciel" , et "Le WTF quotidien" est plein d'exemples pour cela.

Rendez votre modèle de données plus flexible, ignorez les assertions, testez les invariants

Le dernier recours consisterait à rendre votre modèle de données plus flexible. Vous devez ignorer presque toutes les assertions et baser votre modèle de données sur un graphique complet. Comme le montre l'exemple ci-dessus, il est facilement possible d'être votre propre grand-père, vous pouvez donc même avoir des cycles.

Dans ce cas, vous devez tester en profondeur votre logiciel. Vous avez dû ignorer presque toutes les assertions, il y a donc de bonnes chances pour des bogues supplémentaires.

Utilisez un générateur de données de test pour vérifier les cas de test inhabituels. Il existe des bibliothèques de vérification rapide pour Haskell , Erlang ou C . Pour Java / Scala, il y a ScalaCheck et Nyaya . Une idée de test serait de simuler une population aléatoire, de la laisser se croiser au hasard, puis de laisser votre logiciel d'abord importer puis exporter le résultat. On s'attendrait à ce que toutes les connexions dans la sortie soient également dans l'entrée et vice versa.

Un cas où une propriété reste la même est appelé invariant. Dans ce cas, l'invariant est l'ensemble des «relations amoureuses» entre les individus de la population simulée. Essayez de trouver autant d'invariants que possible et testez-les avec des données générées aléatoirement. Les invariants peuvent être fonctionnels, par exemple:

• un oncle reste un oncle, même lorsque vous ajoutez plus de "relations amoureuses"
• chaque enfant a un parent
• une population à deux générations a au moins un grand-parent

Ou ils peuvent être techniques:

• Votre logiciel ne plantera pas sur un graphique jusqu'à 10 milliards de membres (quel que soit le nombre d'interconnexions)
• Votre logiciel évolue avec O (nombre de nœuds) et O (nombre d'arêtes ^ 2)
• Votre logiciel peut enregistrer et recharger chaque graphique de famille jusqu'à 10 milliards de membres

En exécutant les tests simulés, vous trouverez de nombreux cas de coins étranges. Les réparer prendra beaucoup de temps. Vous perdrez également beaucoup d'optimisations, votre logiciel fonctionnera beaucoup plus lentement. Vous devez décider si cela en vaut la peine et si cela est dans la portée de votre logiciel.

Au lieu de supprimer toutes les assertions, vous devriez toujours vérifier des choses comme une personne étant son propre parent ou d'autres situations impossibles et présenter une erreur. Peut-être émettre un avertissement si cela est peu probable afin que l'utilisateur puisse toujours détecter les erreurs de saisie courantes, mais cela fonctionnera si tout est correct.

Je voudrais stocker les données dans un vecteur avec un entier permanent pour chaque personne et stocker les parents et les enfants dans des objets personne où ledit int est l'indice du vecteur. Ce serait assez rapide pour passer d'une génération à l'autre (mais lent pour des choses comme les recherches de noms). Les objets seraient dans l'ordre de leur création.

Dupliquez le père (ou utilisez le lien symbolique / la référence).

Par exemple, si vous utilisez une base de données hiérarchique:

$ #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