Я разработчик программного обеспечения для семейного древа (написано на C ++ и Qt). У меня не было проблем, пока один из моих клиентов не отправил мне сообщение об ошибке. Проблема в том, что у клиента есть двое детей со своей дочерью, и в результате он не может использовать мое программное обеспечение из-за ошибок.

Эти ошибки являются результатом моих различных утверждений и инвариантов об обрабатываемом графе семейства (например, после обхода цикла программа утверждает, что X не может быть и отцом, и дедом Y).

Как я могу устранить эти ошибки, не удаляя все утверждения данных?

Кажется, у вас (и / или вашей компании) есть фундаментальное недопонимание того, каким должно быть семейное древо.

Позвольте уточнить, я также работаю в компании, которая имеет (в качестве одного из своих продуктов) семейное древо в своем портфеле, и мы боролись с подобными проблемами.

Проблема, в нашем случае, и я полагаю, что и ваш случай, исходит из формата GEDCOM , в котором очень сильно выражено мнение о том, какой должна быть семья. Однако этот формат содержит некоторые серьезные заблуждения о том, как на самом деле выглядит семейное древо.

У GEDCOM есть много проблем, таких как несовместимость с однополыми отношениями, инцест и т. Д., Которые в реальной жизни происходят чаще, чем вы думаете (особенно когда возвращаетесь ко времени 1700-1800).

Мы смоделировали наше семейное древо с тем, что происходит в реальном мире: события (например, рождения, свадьбы, помолвки, союзы, смерти, усыновления и т. Д.). Мы не налагаем на них никаких ограничений, за исключением логически невозможных (например, нельзя быть родителем, отношения должны иметь двоих и т. Д.)

Отсутствие проверок дает нам более «реальный мир», более простое и гибкое решение.

Что касается этого конкретного случая, я бы предложил убрать утверждения, поскольку они не являются универсальными.

Для отображения проблем (которые возникнут) я бы предложил рисовать один и тот же узел столько раз, сколько необходимо, намекая на дублирование, подсвечивая все копии при выборе одной из них.

Расслабьте свои утверждения.

Не изменяя правила, которые в большинстве случаев очень полезны для 99,9% ваших клиентов при обнаружении ошибок при вводе их данных.

Вместо этого измените его с ошибки «невозможно добавить связь» на предупреждение с «добавить все равно».

Вот проблема с родословными: они не деревья. Это направленные ациклические графы или DAG. Если я правильно понимаю принципы биологии репродукции человека, циклов не будет.

Насколько я знаю, даже христиане принимают браки (и, следовательно, детей) между двоюродными братьями, что превратит семейное древо в семейный DAG.

Мораль этой истории такова: выбирайте правильные структуры данных.

Я предполагаю, что у вас есть какое-то значение, которое однозначно идентифицирует человека, на котором вы можете основывать свои чеки.

Это хитрый. Предполагая, что вы хотите сохранить структуру дерева, я предлагаю это:

Предположим так: Aесть дети со своей дочерью.

Aдобавляет себя в программу как Aи как B. Оказавшись в роли отца, давайте назовем это парнем.

Добавьте is_same_for_out()функцию, которая сообщает генерирующей выходные данные части вашей программы, что все ссылки, идущие Bвнутри, должны идти Aпри представлении данных.

Это сделает дополнительную работу для пользователя, но я думаю, что ИТ будет относительно легко внедрить и поддерживать.

Основываясь на этом, вы можете работать над синхронизацией кода Aи Bизбежать несоответствий.

Это решение, конечно, не идеально, но это первый подход.

Вы должны сосредоточиться на том, что действительно имеет значение для вашего программного обеспечения . Стоит ли потратить время на то, чтобы заставить его работать на ОДНОГО потребителя стоимость лицензии? Скорее всего нет.

Я советую вам извиниться перед этим клиентом, сказать ему, что его ситуация выходит за рамки вашего программного обеспечения, и вернуть ему деньги.

Вы должны были установить семейство Atreides (современное, Dune или древнее, Oedipus Rex ) в качестве тестового примера. Вы не найдете ошибок, используя очищенные данные в качестве контрольного примера.

Это одна из причин, по которой языки типа «Go» не имеют утверждений. Они используются для обработки случаев, о которых вы, вероятно, даже не задумывались, слишком часто. Вы должны утверждать только невозможное, а не просто невероятное . Именно последнее делает утверждения плохой репутацией. Каждый раз, когда вы печатаете assert(, уходите на десять минут и действительно обдумайте это.

В вашем особенно тревожном случае вполне возможно и ужасно, что такое утверждение будет поддельным при редких, но возможных обстоятельствах. Следовательно, обработайте это в своем приложении, хотя бы для того, чтобы сказать: «Это программное обеспечение не было разработано для обработки сценария, который вы представили».

Утверждать, что твой пра-пра-прадед, будучи твоим отцом, невозможно, - разумная вещь.

Если бы я работал в тестирующей компании, которая была нанята для тестирования вашего программного обеспечения, конечно, я бы представил этот сценарий. Почему? Каждый несовершеннолетний, но умный «пользователь» будет делать то же самое и получать удовольствие от полученного «сообщения об ошибке».

Я ненавижу комментировать такую ​​испорченную ситуацию, но самый простой способ не перестроить все ваши инварианты - это создать фантомную вершину в вашем графе, которая действует как прокси обратно к кровосмесительному отцу.

Итак, я сделал некоторую работу над программным обеспечением генеалогического дерева. Я думаю, что проблема, которую вы пытаетесь решить, заключается в том, что вы должны иметь возможность ходить по дереву, не входя в бесконечные циклы - другими словами, дерево должно быть ациклическим.

Тем не менее, похоже, вы утверждаете, что существует только один путь между человеком и одним из его предков. Это будет гарантировать, что циклов нет, но это слишком строго. Биологически говоря, потомство - это ориентированный ациклический граф (DAG). Случай, который у вас есть, безусловно, вырожденный, но подобные вещи случаются постоянно на больших деревьях.

Например, если вы посмотрите на 2 ^ n предков, которые есть у вас в поколении n, если бы не было перекрытия, то у вас было бы больше предков в 1000 году нашей эры, чем было бы живых людей. Итак, должно быть совпадение.

Тем не менее, вы также склонны получать циклы, которые являются недействительными, просто плохие данные. Если вы пересекаете дерево, то нужно разобраться с циклами. Вы можете сделать это в каждом отдельном алгоритме или при загрузке. Я сделал это под нагрузкой.

Найти истинные циклы в дереве можно несколькими способами. Неправильный способ состоит в том, чтобы пометить каждого предка от данного человека, и при прохождении, если человек, которому вы собираетесь перейти к следующему, уже отмечен, тогда обрежьте ссылку. Это разорвет потенциально точные отношения. Правильный способ сделать это - начать с каждого человека и пометить каждого предка путем к этому человеку. Если новый путь содержит текущий путь в качестве подпути, то это цикл, и его следует разорвать. Вы можете хранить пути как вектор <bool> (MFMF, MFFFMF и т. Д.), Что делает сравнение и хранение очень быстрым.

Есть несколько других способов обнаружения циклов, таких как отправка двух итераторов и проверка, не сталкиваются ли они когда-либо с тестом подмножества, но в итоге я использовал метод локального хранилища.

Также обратите внимание, что вам не нужно фактически разрывать ссылку, вы можете просто изменить ее с обычной ссылки на «слабую», за которой не следуют некоторые ваши алгоритмы. Вы также захотите позаботиться о выборе ссылки, которая будет отмечена как слабая; иногда вы можете выяснить, где цикл должен быть нарушен, посмотрев информацию о дате рождения, но часто вы не можете ничего выяснить, потому что отсутствует так много данных.

Еще один серьезный серьезный ответ на глупый вопрос:

Реальный ответ: используйте соответствующую структуру данных. Человеческая родословная не может быть полностью выражена с использованием чистого дерева без циклов. Вы должны использовать какой-то график. Кроме того, поговорите с антропологом, прежде чем идти дальше с этим, потому что во многих других местах подобные ошибки могут быть допущены при моделировании генеалогии, даже в самом простом случае «западно-патриархального моногамного брака».

Даже если мы хотим игнорировать локально запретные отношения, как обсуждалось здесь, существует множество совершенно законных и совершенно неожиданных способов введения циклов в семейное древо.

Например: http://en.wikipedia.org/wiki/Cousin_marriage

По сути, браки между двоюродными братьями не только обычны и ожидаемы, именно поэтому люди прошли путь от тысяч небольших семейных групп до мирового населения в 6 миллиардов человек. Это не может работать по-другому.

На самом деле очень мало универсалов, когда дело доходит до генеалогии, семьи и родословной. Почти любое строгое предположение о нормах, указывающих на то, кем может быть тетя или кто может жениться на ком или как дети узаконены с целью наследования, может быть нарушено каким-то исключением где-то в мире или истории.

За исключением потенциальных правовых последствий, вам, безусловно, нужно рассматривать «узел» на семейном дереве как человека-предшественника, а не предполагать, что этот узел может быть единственным человеком.

Сделайте так, чтобы узел дерева включал в себя как человека, так и его преемников - и тогда вы можете иметь еще один узел, находящийся глубже в дереве, в который входит один и тот же человек с разными преемниками.

Несколько ответов показали способы сохранить утверждения / инварианты, но это выглядит как неправильное использование утверждений / инвариантов. Утверждения должны гарантировать, что то, что должно быть правдой, является истинным, а инварианты должны гарантировать, что то, что не должно измениться, не изменяется.

Здесь вы утверждаете, что кровосмесительных отношений не существует. Ясно , что они делают существует, так что ваше утверждение является недействительным. Вы можете обойти это утверждение, но настоящая ошибка заключается в самом утверждении. Утверждение должно быть удалено.

Ваше генеалогическое древо должно использовать направленные отношения. Таким образом, у вас не будет цикла.

Генеалогические данные являются циклическими и не вписываются в ациклический граф, поэтому, если у вас есть утверждения против циклов, вы должны удалить их.

Способ обработки этого в представлении без создания настраиваемого представления состоит в том, чтобы обрабатывать циклический родительский элемент как «призрачный» родительский элемент. Другими словами, когда человек является и отцом, и дедом для одного и того же человека, тогда узел дедушки отображается нормально, но узел отца отображается как «призрачный» узел, который имеет простую метку, например («см. Дед» ) и указывает на дедушку.

Для выполнения вычислений вам может потребоваться улучшить логику обработки циклических графов, чтобы узел не посещался более одного раза, если есть цикл.

Самое главное avoid creating a problem, поэтому я считаю, что вы должны использовать прямое отношение, чтобы избежать цикла.

Как сказал @markmywords, #include "fritzl.h".

Наконец я должен сказать recheck your data structure. Возможно, что-то там не так (возможно, двунаправленный связанный список решает вашу проблему).

Утверждения не выживают в реальности

Обычно утверждения не выдерживают контакта с данными реального мира. Это часть процесса разработки программного обеспечения, чтобы решить, с какими данными вы хотите иметь дело, а какие нет.

Циклические семейные графы

Относительно семейных «деревьев» (на самом деле это полноразмерные графы, включая циклы), есть хороший анекдот:

Я женился на вдове, у которой была взрослая дочь. Мой отец, который часто посещал нас, влюбился в мою падчерицу и женился на ней. В результате мой отец стал моим сыном, а моя дочь стала моей матерью. Некоторое время спустя я подарил своей жене сына, который был братом моего отца, и моего дядю. У жены моего отца (которая также является моей дочерью и моей матерью) родился сын. В результате я получил брата и внука в одном лице. Моя жена теперь моя бабушка, потому что она мама моей мамы. Итак, я муж моей жены и одновременно внук моей жены. Другими словами, я мой собственный дедушка.

Все становится еще более странным, если принять во внимание суррогаты или «нечеткое отцовство».

Как с этим бороться

Определить циклы как выходящие за рамки

Вы можете решить, что ваше программное обеспечение не должно иметь дело с такими редкими случаями. В таком случае пользователь должен использовать другой продукт. Это делает работу с более распространенными случаями гораздо более надежной, поскольку вы можете сохранить больше утверждений и более простую модель данных.

В этом случае добавьте некоторые хорошие функции импорта и экспорта в свое программное обеспечение, чтобы при необходимости пользователь мог легко перейти на другой продукт.

Разрешить ручные отношения

Вы можете позволить пользователю добавлять ручные отношения. Эти отношения не являются «первоклассными гражданами», то есть программное обеспечение принимает их как есть, не проверяет их и не обрабатывает их в основной модели данных.

Затем пользователь может обрабатывать редкие случаи вручную. Ваша модель данных все еще останется довольно простой, и ваши утверждения выживут.

Будьте осторожны с ручными отношениями. Существует соблазн сделать их полностью настраиваемыми и, следовательно, создать полностью настраиваемую модель данных. Это не будет работать: ваше программное обеспечение не будет масштабироваться, вы получите странные ошибки и, наконец, пользовательский интерфейс станет непригодным для использования. Этот анти-паттерн называется «мягким кодированием» , и «Ежедневный WTF» полон примеров для этого.

Сделайте вашу модель данных более гибкой, пропустите утверждения, протестируйте инварианты

В крайнем случае, ваша модель данных будет более гибкой. Вам придется пропустить почти все утверждения и основывать свою модель данных на полномасштабном графике. Как показывает приведенный выше пример, легко быть вашим собственным дедом, поэтому вы можете даже иметь циклы.

В этом случае вам следует тщательно протестировать свое программное обеспечение. Вы должны были пропустить почти все утверждения, так что есть хороший шанс для дополнительных ошибок.

Используйте генератор тестовых данных для проверки необычных тестовых случаев. Есть быстрые библиотеки проверки на Haskell , Erlang или C . Для Java / Scala есть ScalaCheck и ньяя . Одной из проверочных идей будет симуляция случайной популяции, случайное скрещивание, затем сначала ваше программное обеспечение импортирует, а затем экспортирует результат. Ожидалось бы, что все соединения на выходе также находятся на входе и наоборот.

Случай, когда свойство остается неизменным, называется инвариантом. В этом случае инвариант - это набор «романтических отношений» между индивидами в моделируемой популяции. Постарайтесь найти как можно больше инвариантов и протестируйте их со случайно сгенерированными данными. Инварианты могут быть функциональными, например:

• дядя остается дядей, даже когда вы добавляете больше "романтических отношений"
• у каждого ребенка есть родитель
• население с двумя поколениями имеет по крайней мере одного прародителя

Или они могут быть техническими:

• Ваше программное обеспечение не будет зависать на графике до 10 миллиардов участников (независимо от того, сколько соединений)
• Ваше программное обеспечение масштабируется с O (количество узлов) и O (количество ребер ^ 2)
• Ваше программное обеспечение может сохранять и перезагружать каждый семейный граф до 10 миллиардов участников.

Запустив смоделированные тесты, вы обнаружите множество странных угловых случаев. Их исправление займет много времени. Также вы потеряете много оптимизаций, ваше программное обеспечение будет работать намного медленнее. Вы должны решить, стоит ли оно того и входит ли оно в сферу вашего программного обеспечения.

Вместо того, чтобы удалять все утверждения, вы все равно должны проверить наличие таких вещей, как человек, являющийся его / ее собственным родителем, или других невозможных ситуаций и представить ошибку. Может быть, выдает предупреждение, если это маловероятно, так что пользователь все еще может обнаружить общие ошибки ввода, но это будет работать, если все правильно.

Я бы сохранял данные в векторе с постоянным целым числом для каждого человека и сохранял бы родителей и детей в объектах person, где указанное int является индексом вектора. Это было бы довольно быстро, чтобы идти между поколениями (но медленно для таких вещей, как поиск по имени). Объекты будут в порядке, когда они были созданы.

Дублируйте отца (или используйте символическую ссылку / ссылку).

Например, если вы используете иерархическую базу данных:

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