c++ nome Ciclos no software da árvore genealógica



arvore genealogica da familia (15)

Eu sou o desenvolvedor de algum software de árvore genealógica (escrito em C ++ e Qt). Eu não tive problemas até que um dos meus clientes me enviou um relatório de bug. O problema é que o cliente tem dois filhos com sua própria filha e, como resultado, ele não pode usar meu software por causa de erros.

Esses erros são o resultado de minhas várias asserções e invariantes sobre o gráfico da família sendo processado (por exemplo, depois de percorrer um ciclo, o programa afirma que X não pode ser pai e avô de Y).

Como posso resolver esses erros sem remover todas as asserções de dados?


Answer #1

Possíveis implicações legais à parte, certamente parece que você precisa tratar um 'nó' em uma árvore genealógica como uma pessoa predecessora, em vez de assumir que o nó pode ser a única pessoa.

Faça com que o nó da árvore inclua uma pessoa assim como os sucessores - e então você pode ter outro nó mais abaixo na árvore que inclui a mesma pessoa com sucessores diferentes.


Answer #2

Esta é uma das razões pelas quais linguagens como "Go" não têm asserções. Eles são usados ​​para lidar com casos que você provavelmente não pensou, com muita frequência. Você só deve afirmar o impossível, não simplesmente o improvável . Fazer o segundo é o que dá às afirmações uma má reputação. Toda vez que você digita assert( , fique fora por dez minutos e realmente pense nisso.

Em seu caso particularmente perturbador, é concebível e chocante que tal afirmação seja falsa sob circunstâncias raras, mas possíveis. Por isso, lide com isso no seu aplicativo, se apenas para dizer "Este software não foi projetado para lidar com o cenário que você apresentou".

Afirmar que seu grande, grande bisavô sendo seu pai como impossível é uma coisa razoável a ser feita.

Se eu estivesse trabalhando para uma empresa de testes que foi contratada para testar seu software, é claro que eu teria apresentado esse cenário. Por quê? Todo usuário jovem, mas inteligente, vai fazer exatamente a mesma coisa e se deliciar com o "relatório de bugs" resultante.


Answer #3

Eu acho que você tem algum valor que identifica exclusivamente uma pessoa em que você pode basear seus cheques.

Isso é complicado. Supondo que você queira manter a estrutura de uma árvore, sugiro isso:

Assuma isso: A tem filhos com sua própria filha.

A adiciona-se ao programa como A e como B Uma vez no papel de pai, vamos chamá-lo de namorado.

Adicione uma função is_same_for_out() que diga à parte geradora de saída de seu programa que todos os links que vão para B internamente devem ir para A na apresentação dos dados.

Isso vai fazer algum trabalho extra para o usuário, mas eu acho que seria relativamente fácil de implementar e manter.

Com base nisso, você poderia trabalhar em sincronização de código A e B para evitar inconsistências.

Essa solução certamente não é perfeita, mas é uma primeira abordagem.


Answer #4

Sua árvore genealógica deve usar relações direcionadas. Desta forma você não terá um ciclo.


Answer #5

Parece que você (e / ou sua empresa) tem um mal-entendido fundamental sobre o que é uma árvore genealógica.

Deixe-me esclarecer, eu também trabalho para uma empresa que tem (como um dos seus produtos) uma árvore genealógica em sua carteira, e nós temos lutado com problemas semelhantes.

O problema, no nosso caso, e eu também assumo o seu caso, vem do formato GEDCOM que é extremamente opinativo sobre o que uma família deveria ser. No entanto, este formato contém alguns equívocos severos sobre como uma árvore genealógica realmente se parece.

O GEDCOM tem muitos problemas, como incompatibilidade com relações do mesmo sexo, incesto, etc ... O que na vida real acontece com mais freqüência do que você imagina (especialmente quando voltando no tempo para 1700-1800).

Nós modelamos nossa árvore genealógica para o que acontece no mundo real: Eventos (por exemplo, nascimentos, casamentos, noivado, uniões, mortes, adoções, etc.). Nós não colocamos quaisquer restrições sobre estes, exceto para os logicamente impossíveis (por exemplo, um não pode ser o próprio pai, relações precisam de dois indivíduos, etc ...)

A falta de validações nos dá uma solução mais "real", mais simples e mais flexível.

Quanto a esse caso específico, sugiro remover as afirmações, pois elas não são válidas universalmente.

Para exibir problemas (que surgirão), sugiro desenhar o mesmo nó quantas vezes forem necessárias, insinuando a duplicação, iluminando todas as cópias ao selecionar uma delas.


Answer #6

Outra falsa resposta séria para uma pergunta boba:

A verdadeira resposta é usar uma estrutura de dados apropriada. A genealogia humana não pode ser totalmente expressa usando uma árvore pura sem ciclos. Você deve usar algum tipo de gráfico. Além disso, converse com um antropólogo antes de prosseguir com isso, porque há muitos outros lugares que podem ser cometidos erros semelhantes tentando modelar a genealogia, mesmo no caso mais simples de "casamento monogâmico patriarcal ocidental".

Mesmo se quisermos ignorar as relações de tabu local, como discutido aqui, há muitas maneiras perfeitamente legais e completamente inesperadas de introduzir ciclos em uma árvore genealógica.

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

Basicamente, o casamento entre primos não é apenas comum e esperado, é a razão pela qual os humanos passaram de milhares de pequenos grupos familiares para uma população mundial de 6 bilhões. Não pode funcionar de outra maneira.

Realmente existem muito poucos universais quando se trata de genealogia, família e linhagem. Quase qualquer suposição estrita sobre as normas que sugerem quem uma tia pode ser, ou quem pode casar com quem, ou como as crianças são legitimadas para fins de herança, pode ser perturbada por alguma exceção em algum lugar do mundo ou da história.


Answer #7

Você deveria ter criado a família Atreides (moderna, Atreides ou antiga, Oedipus Rex ) como um caso de teste. Você não encontra bugs usando dados higienizados como um caso de teste.


Answer #8

Algumas respostas mostraram maneiras de manter as asserções / invariantes, mas isso parece um mau uso de asserções / invariantes. As asserções são para garantir que algo que deveria ser verdade seja verdade, e invariantes são para garantir que algo que não deveria mudar não mude.

O que você está afirmando aqui é que relacionamentos incestuosos não existem. Claramente eles existem, então sua afirmação é inválida. Você pode contornar essa afirmação, mas o bug real está na própria afirmação. A afirmação deve ser removida.


Answer #9

Eu odeio comentar sobre uma situação tão complicada, mas a maneira mais fácil de não reconquistar todos os seus invariantes é criar um vértice fantasma em seu gráfico que atue como um proxy para o pai incestuoso.


Answer #10

O mais importante é avoid creating a problem , por isso acredito que você deve usar uma relação direta para evitar um ciclo.

Como disse @mymywords, #include "fritzl.h".

Finalmente eu tenho que dizer recheck your data structure . Talvez algo esteja errado por aí (talvez uma lista vinculada bidirecional resolva seu problema).


Answer #11

Em vez de remover todas as asserções, você deve verificar se há coisas como uma pessoa sendo mãe ou outras situações impossíveis e apresentar um erro. Talvez emita um aviso se for improvável, para que o usuário ainda possa detectar erros de entrada comuns, mas funcionará se tudo estiver correto.

Gostaria de armazenar os dados em um vetor com um inteiro permanente para cada pessoa e armazenar os pais e filhos em objetos pessoais, onde o dito int é o índice do vetor. Isso seria muito rápido para ir entre gerações (mas lento para coisas como pesquisas de nome). Os objetos estariam na ordem de quando foram criados.


Answer #12

Você deve se concentrar no que realmente agrega valor ao seu software . O tempo gasto para fazer com que funcione para UM consumidor vale o preço da licença? Provavelmente não.

Aconselho-o a pedir desculpas a este cliente, dizer-lhe que a sua situação está fora do âmbito do seu software e emitir um reembolso.


Answer #13

Relaxe suas afirmações.

Não mudando as regras, que provavelmente são muito úteis para 99,9% dos seus clientes em pegar erros ao inserir seus dados.

Em vez disso, altere-o de um erro "não é possível adicionar um relacionamento" a um aviso com um "add anyway".


Answer #14

Afirmações não sobrevivem à realidade

Normalmente, as afirmações não sobrevivem ao contato com dados do mundo real. É uma parte do processo de engenharia de software decidir com quais dados você quer lidar e quais estão fora do escopo.

Gráficos familiares cíclicos

Em relação às "árvores" familiares (na verdade são gráficos completos, incluindo ciclos), há uma boa história:

Eu me casei com uma viúva que tinha uma filha adulta. Meu pai, que muitas vezes nos visitava, se apaixonou pela minha enteada e se casou com ela. Como resultado, meu pai se tornou meu filho e minha filha se tornou minha mãe. Algum tempo depois, dei à minha esposa um filho, que era irmão de meu pai e meu tio. A esposa do meu pai (que também é minha filha e minha mãe) tem um filho. Como resultado, consegui um irmão e um neto na mesma pessoa. Minha esposa é agora minha avó, porque ela é mãe da minha mãe. Então eu sou o marido da minha esposa e, ao mesmo tempo, o neto da minha esposa. Em outras palavras, eu sou meu próprio avô.

As coisas ficam ainda mais estranhas quando você considera os surrogates ou a "paternidade difusa".

Como lidar com isso

Definir ciclos como fora do escopo

Você pode decidir que seu software não deve lidar com casos tão raros. Se tal caso ocorrer, o usuário deve usar um produto diferente. Isso faz com que lidar com os casos mais comuns seja muito mais robusto, porque você pode manter mais asserções e um modelo de dados mais simples.

Nesse caso, adicione alguns recursos bons de importação e exportação ao seu software, para que o usuário possa migrar facilmente para um produto diferente, quando necessário.

Permitir relações manuais

Você pode permitir que o usuário adicione relações manuais. Essas relações não são "cidadãos de primeira classe", ou seja, o software os considera como estão, não os verifica e não os manipula no modelo de dados principal.

O usuário pode lidar com casos raros manualmente. Seu modelo de dados ainda permanecerá bastante simples e suas afirmações sobreviverão.

Tenha cuidado com as relações manuais. Há uma tentação de torná-los completamente configuráveis ​​e, portanto, criar um modelo de dados totalmente configurável. Isso não funcionará: seu software não será dimensionado, você receberá bugs estranhos e, finalmente, a interface do usuário ficará inutilizável. Esse anti-padrão é chamado de "soft coding" , e "The daily WTF" é cheio de exemplos para isso.

Torne seu modelo de dados mais flexível, pule asserções, teste invariantes

O último recurso seria tornar seu modelo de dados mais flexível. Você teria que pular quase todas as asserções e basear seu modelo de dados em um gráfico completo. Como o exemplo acima mostra, é facilmente possível ser seu próprio avô, então você pode até ter ciclos.

Neste caso, você deve testar extensivamente seu software. Você teve que pular quase todas as asserções, então há uma boa chance de erros adicionais.

Use um gerador de dados de teste para verificar casos de teste incomuns. Existem bibliotecas de verificação rápida para Haskell , Erlang ou C Para Java / Scala, há ScalaCheck e Nyaya . Uma ideia de teste seria simular uma população aleatória, deixar que ela se intercruzasse aleatoriamente e deixar o software primeiro importar e depois exportar o resultado. A expectativa seria que todas as conexões na saída também estejam na entrada e vice versa.

Um caso em que uma propriedade permanece igual é chamado de invariante. Nesse caso, o invariante é o conjunto de "relações românticas" entre os indivíduos da população simulada. Tente encontrar o máximo possível de invariantes e teste-os com dados gerados aleatoriamente. Invariantes podem ser funcionais, por exemplo:

  • um tio fica um tio, mesmo quando você adiciona mais "relações românticas"
  • toda criança tem um pai
  • uma população com duas gerações tem pelo menos um avô

Ou eles podem ser técnicos:

  • Seu software não irá falhar em um gráfico de até 10 bilhões de membros (não importa quantas interconexões)
  • Seu software é dimensionado com O (number-of-nodes) e O (number-of-edges ^ 2)
  • Seu software pode salvar e recarregar todos os gráficos de famílias de até 10 bilhões de membros

Ao executar os testes simulados, você encontrará muitos casos estranhos de canto. Consertá-los levará muito tempo. Além disso, você perderá muitas otimizações, seu software rodará muito mais devagar. Você tem que decidir, se vale a pena e se isso está no escopo do seu software.


Answer #15

Aqui está o problema com as árvores genealógicas: elas não são árvores. Eles são gráficos acíclicos dirigidos ou DAGs. Se eu entendi os princípios da biologia da reprodução humana corretamente, não haverá ciclos.

Tanto quanto sei, até os cristãos aceitam casamentos (e, portanto, filhos) entre primos, que transformarão a árvore genealógica em uma família DAG.

A moral da história é: escolha as estruturas de dados corretas.





family-tree