Вопрос: Циклы в программном обеспечении семейства деревьев


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

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

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


1594


источник


Ответы:


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

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

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

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

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

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

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

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


727



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

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

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


564



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

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

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


224



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

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

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

Aдобавляет себя в программу как Aи в качестве B, Однажды в роли отца, назовем его парнем.

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

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

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

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


115



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

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


84



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


79



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

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

Утверждение, что ваш великий, великий, прадед, являющийся вашим отцом как невозможным, является разумным делом.

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


59



I hate commenting on such a screwed up situation, but the easiest way to not rejigger all of your invariants is to create a phantom vertex in your graph that acts as a proxy back to the incestuous dad.


41



So, I've done some work on family tree software. I think the problem you're trying to solve is that you need to be able to walk the tree without getting in infinite loops - in other words, the tree needs to be acyclical.

However, it looks like you're asserting that there is only one path between a person and one of their ancestors. That will guarantee that there are no cycles, but is too strict. Biologically speaking, descendancy is a directed acyclic graph (DAG). The case you have is certainly a degenerate case, but that type of thing happens all the time on larger trees.

For example, if you look at the 2^n ancestors you have at generation n, if there was no overlap, then you'd have more ancestors in 1000 AD than there were people alive. So, there's got to be overlap.

However, you also do tend to get cycles that are invalid, just bad data. If you're traversing the tree, then cycles must be dealt with. You can do this in each individual algorithm, or on load. I did it on load.

Finding true cycles in a tree can be done in a few ways. The wrong way is to mark every ancestor from a given individual, and when traversing, if the person you're going to step to next is already marked, then cut the link. This will sever potentially accurate relationships. The correct way to do it is to start from each individual, and mark each ancestor with the path to that individual. If the new path contains the current path as a subpath, then it's a cycle, and should be broken. You can store paths as vector<bool> (MFMF, MFFFMF, etc.) which makes the comparison and storage very fast.

There are a few other ways to detect cycles, such as sending out two iterators and seeing if they ever collide with the subset test, but I ended up using the local storage method.

Also note that you don't need to actually sever the link, you can just change it from a normal link to a 'weak' link, which isn't followed by some of your algorithms. You will also want to take care when choosing which link to mark as weak; sometimes you can figure out where the cycle should be broken by looking at birthdate information, but often you can't figure out anything because so much data is missing.


37



Another mock serious answer for a silly question:

The real answer is, use an appropriate data structure. Human genealogy cannot fully be expressed using a pure tree with no cycles. You should use some sort of graph. Also, talk to an anthropologist before going any further with this, because there are plenty of other places similar errors could be made trying to model genealogy, even in the most simple case of "Western patriarchal monogamous marriage."

Even if we want to ignore locally taboo relationships as discussed here, there are plenty of perfectly legal and completely unexpected ways to introduce cycles into a family tree.

For example: http://en.wikipedia.org/wiki/Cousin_marriage

Basically, cousin marriage is not only common and expected, it is the reason humans have gone from thousands of small family groups to a worldwide population of 6 billion. It can't work any other way.

There really are very few universals when it comes to genealogy, family and lineage. Almost any strict assumption about norms suggesting who an aunt can be, or who can marry who, or how children are legitimized for the purpose of inheritance, can be upset by some exception somewhere in the world or history.


36



Potential legal implications aside, it certainly seems that you need to treat a 'node' on a family tree as a predecessor-person rather than assuming that the node can be the-one-and-only person.

Have the tree node include a person as well as the successors - and then you can have another node deeper down the tree that includes the same person with different successors.


20



A few answers have shown ways to keep the assertions/invariants, but this seems like a misuse of assertions/invariant. Assertions are to make sure something that should be true is true, and invariants are to make sure something that shouldn't change doesn't change.

What you're asserting here is that incestuous relationships don't exist. Clearly they do exist, so your assertion is invalid. You can work around this assertion, but the real bug is in the assertion itself. The assertion should be removed.


13