Question Cycles dans le logiciel de l'arbre généalogique


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'a envoyé un rapport de bogue. Le problème est que le client a deux enfants avec sa propre fille, et, par conséquent, il ne peut pas utiliser mon logiciel à cause d'erreurs.

Ces erreurs sont le résultat de mes diverses affirmations et invariants sur le graphe de famille traité (par exemple, après avoir parcouru un cycle, le programme indique 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?


1594
2018-05-28 18:39


origine


Réponses:


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

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

Le problème, dans notre cas, et je présume que votre cas vient également de GEDCOM format qui est extrêmement opiniâtre sur ce que devrait être une famille. Cependant, ce format contient des idées fausses sur ce à quoi ressemble vraiment un arbre généalogique.

GEDCOM a de nombreux problèmes, tels que l'incompatibilité avec les relations de même sexe, l'inceste, etc ... Ce qui dans la vraie vie se produit plus souvent que vous ne l'imaginez (surtout en remontant dans le temps à la période 1700-1800).

Nous avons modélisé notre arbre généalogique à ce qui se passe dans le monde réel: les événements (par exemple, les naissances, les mariages, l'engagement, les unions, les décès, les adoptions, etc.). Nous n'imposons aucune restriction à ceux-ci, sauf pour ceux qui sont logiquement impossibles (par exemple, on ne peut pas être son propre parent, les relations ont besoin de deux individus, etc ...)

Le manque de validations nous donne une solution plus "réelle", plus simple et plus flexible.

En ce qui concerne ce cas particulier, je suggère de supprimer les assertions car elles ne sont pas universelles.

Pour afficher les problèmes (qui surviendront), je suggérerais de dessiner le même nœud autant de fois que nécessaire, faisant allusion à la duplication en allumant toutes les copies en sélectionnant l'une d'entre elles.


727
2018-06-01 08:25



Détendez vos affirmations.

Pas en changeant les règles, qui sont très probablement très utiles à 99,9% de vos clients dans la saisie des erreurs dans la saisie de leurs données.

Au lieu de cela, changez-le d'une erreur "ne peut pas ajouter de relation" à un avertissement avec un "ajouter de toute façon".


564
2018-05-28 19:20



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

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.


224
2018-06-01 09:58



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

C'est un problème. En supposant que vous voulez garder la structure d'un arbre, je suggère ceci:

Supposons ceci: A a des enfants avec sa propre fille.

A ajoute lui-même au programme A et comme B. Une fois dans le rôle de père, appelons-le petit ami.

Ajouter un is_same_for_out() fonction qui indique la partie de production de sortie de votre programme que tous les liens vont à B en interne devrait aller à A sur présentation des données.

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

Construire à partir de cela, vous pouvez travailler sur la synchronisation de code A et B pour éviter les incohérences.

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


115
2018-05-28 18:50



Vous devriez vous concentrer sur ce qui fait vraiment de la valeur pour votre logiciel. Est-ce que le temps passé à le faire fonctionner pour un consommateur vaut 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 pour votre logiciel et lui faire un remboursement.


84
2018-06-01 08:51



Vous devriez avoir mis en place le Atreides famille (soit moderne, Duneou antique Œdipe Rex) comme un cas de test. Vous ne trouvez pas de bogues en utilisant des données aseptisées comme cas de test.


79
2018-06-01 16:10



C'est une des raisons pour lesquelles les 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 devriez seulement affirmer 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(, partez pour dix minutes et vraiment penses-y.

Dans votre cas particulièrement troublant, il est à la fois concevable et effroyable qu'une telle affirmation soit fausse dans des circonstances rares mais possibles. Par conséquent, le gérer 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 soit votre père aussi impossible est une chose raisonnable à faire.

Si je travaillais pour une société de test qui a été 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 savourez dans le 'rapport de bogue' qui en résulte.


59
2018-06-01 06:10



Je déteste commenter une telle situation foirée, mais la façon la plus simple de ne pas réorganiser tous vos invariants est de créer un sommet fantôme dans votre graphique qui agit comme un proxy pour le père incestueux.


41
2018-05-28 18:55



J'ai donc travaillé sur le logiciel de l'arbre généalogique. Je pense que le problème que vous essayez de résoudre est que vous devez être capable de marcher dans l'arbre sans passer par des 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 un de ses ancêtres. Cela garantira qu'il n'y a pas de cycles, mais 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 arrive tout le temps sur les grands arbres.

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 après JC que de personnes vivantes. Donc, il doit y avoir un chevauchement.

Cependant, vous avez aussi tendance à avoir des cycles invalides, juste de mauvaises données. Si vous traversez l'arbre, alors 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 être fait de plusieurs façons. La mauvaise façon est de marquer chaque ancêtre d'un individu donné, et lors de la traversée, si la personne que vous allez passer à la suivante est déjà marquée, alors coupez le lien. Cela va couper les relations potentiellement précises. La bonne façon de le faire est de commencer à partir de chaque individu, et marquer chaque ancêtre avec le chemin de cet individu. Si le nouveau chemin contient le chemin courant comme sous-chemin, alors c'est un cycle, et devrait être cassé. Vous pouvez stocker des chemins comme vecteur <bool> (MFMF, MFFFMF, etc.) ce qui rend la comparaison et le stockage très rapides.

Il existe quelques autres moyens de détecter les cycles, comme l'envoi de deux itérateurs et de voir s'ils entrent en 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 découper le lien, vous pouvez juste le changer d'un lien normal à un lien «faible», qui n'est pas suivi par certains de vos algorithmes. Vous devrez également faire attention en choisissant quel lien marquer comme faible; Parfois, vous pouvez déterminer où le cycle doit être brisé en regardant les informations sur les dates de naissance, mais souvent vous ne pouvez rien comprendre parce qu'il manque tellement de données.


37
2018-06-01 18:39