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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предположим следующее: у A есть дети от собственной дочери.

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

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

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

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

Это решение, безусловно, не идеально, но это первый подход.

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

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

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

Это одна из причин, почему в таких языках, как 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