И снова о генеалогических деревьях
Источник: Kandinksy 2.2 (fusionbrain.ai)
Когда в очередной раз меня охватило желание собрать всю информацию по своим родственникам, я стал подробно смотреть на доступные инструменты. Основное, что предлагается широкому потребителю, это книги с выделенными листами под того или иного родственника. Надо ли говорить, что никакую структуру родства описать таким образом не получится, и максимум что можно в такой формат уместить, это, пожалуй, только родители, дети, бабушки, дедушки и браться с сестрами. Иными словами, непосредственные родственники, а для прародителей и каких-нибудь двоюродных теть такой формат уже не подходит совсем, — степень родства придется описывать словами, и вместо структуры получится каша.
Итак, мне захотелось визуализировать каким-то вменяемым образом свое генеалогическое дерево, включив туда всех прямых и непрямых родственников, о которых хоть что-нибудь известно. Данная статья описывает подходы к этой задаче, полученные результаты и ряд интересных вопросов, которые возникают при более глубоком погружении в эту тему. Все алгоритмы и отрисовка были реализованы на python из-за удобства работы со списками и словарями. Код носит базовый характер, связанный со структурами данных, их обработкой и самой простой визуализацией. Конечно же, изложенный подход можно упаковать в интересный продукт, о чем также пару слов будет сказано в конце статьи. Поехали.
Построение дерева
В качестве отправной точки для построения генеалогического дерева для той или иной группы людей необходимо понять, каким образом должны быть структурированы входные данные по ним. Если следовать логике книжного каталога, то подход такой — для каждого человека заводим группу атрибутов, один или несколько из которых обозначает какую-либо родственную связь с другими людьми. Причем эта связь может быть какой угодно — ребенок, родитель, брат, дедушка и так далее. Однако быстро становится понятно, что описать таким образом большое разнообразие родственных связей сложно, а для отдаленных родственников и невозможно (как назвать мать жены троюродного брата вашего прапрадедушки?). То есть в тексте описать можно, но системно выстраивать иерархию в виде дерева на такой основе не получится. Поэтому необходим некоторый минимальный элемент родства, на основе которого можно было бы воссоздать всю структуру. А это, конечно же, родство между родителем и ребенком. Во-первых, у каждого живущего или когда-либо жившего есть или были и мать и отец, а во-вторых, все прочие виды родства выводятся из данного. Таким образом, в качестве входных данных для построения дерева будем использовать таблицу с двумя колонками, по строкам которой задаются упорядоченные пары «родитель-ребенок». Для простоты в ячейках таблицы указывается единственный атрибут соответствующего узла дерева — строка с фамилией, именем и отчеством.
Далее возникает задача построения дерева иерархии родства на основе пар «родитель-ребенок». Интуитивно хотелось бы, чтобы в дереве выделялись бы уровни, примерно соответствующие временной шкале и выделяющие поколения — чем дальше от нас отстоит родственник во времени, тем дальше он бы находился от нас и в дереве. Казалось бы, это получается само собой — например, между вами и вашей прабабушкой точно будут находиться еще бабушка и мама. Но такое верно только для прямого родства — если, скажем, у прабабушки была бездетная сестра, ее положение в дереве зависит от алгоритма его построения (забегая вперед, можно сказать, что два основных фактора, осложняющих построение дерева, это как раз бездетные родственники в предшествующих поколениях, а также ситуации неполнородных братьев и сестер). Так естественным образом для узлов дерева возникает понятие ранга, что-то вроде поколения. Если у ребенка ранг 1, то у его родителей ранг 2, а у бабушек и дедушек — ранг 3, и так далее. Зная ранги каждого узла, можно будет отрисовать дерево в виде многодольного графа, например, внизу располагая самых младших представителей генеалогии с наименьшим рангом и двигаясь наверх вглубь времен, добавляя все более старшие ранги и связи между ними.
Как можно распределить узлы по рангам? Первый вариант, который я пробовал, все еще держа в голове неверное представление о результирующем графе как именно о дереве — проход от каждого не имеющего детей узла по предкам наверх. В исходной таблице пар «родитель-ребенок» находим все узлы, которые есть только в колонке «ребенок», присваиваем им ранг 0 и идем к их родителям. Родителям присваиваем ранг 1 и идем к уже их родителям, которым присваиваем ранг 2, и так далее. Такая схема работает только в самом простом случае. Если, например, у вашего папы есть родной брат, у которого нет детей, он получит ранг 0, что кажется некорректным, так как все же это поколение вашего отца. Поэтому требуется повторный проход сверху вниз от родственников, для которых нет никакой информации об их родителях (в моем случае это пра-пра-прадедушки), с уменьшением ранга на 1 и его перезаписью, если у узла уже был назначен меньший ранг. К сожалению, жизнь штука еще более сложная, и даже два прохода не устраняют некорректное назначение рангов в ситуациях неполнородных братьев и сестер (где общие только мама или только папа). При включении таких веток родства в генеалогию невозможно для произвольно заданной таблицы пар «родитель-ребенок» вычислить количество требуемых проходов вверх и вниз. Поэтому в итоге я пришел к варианту с распространением волны.
Распространение волны рангов можно начать с любого узла. Назначаем ему произвольное стартовое значение ранга, для его родителей (при наличии) — ранг на единицу больше, для его детей (при наличии) — на единицу меньше. Исходим из того, что информация по родственникам такова, что а) из любого узла дерева можно по связям перейти в любой другой узел и б) в результирующем графе отсутствуют циклы. Наличие циклов сильно усложняет задачу и, возможно, рушит всю идею с рангами и красивой поуровневой отрисовкой дерева, но это ситуации довольно специфические. Итеративно осуществляем переходы для непосредственных предков и потомков и в итоге получаем назначенные ранги для всех узлов, что позволяет нам перейти к визуализации дерева.
Отрисовка дерева
Отрисовка дерева при известных рангах для узлов носит в целом технический характер, за исключением проблемы пересечений. Для иллюстрации данной проблемы посмотрим на обезличенное генеалогическое дерево, которое я построил на данных о своих родственниках:
Рис. 1. Граф без оптимизации числа пересечений
Как видно, граф получился достаточно запутанным. При этом перестановки узлов с одинаковым рангом (внутри уровней) эту запутанность могут как-то менять. Можно ввести метрику — количество пересекающихся связей в графе. Причем, так как связи в данном графе присутствуют строго между соседними уровнями (внутри уровня и с прыжком через несколько уровней их нет), можно анализировать не только общую сумму пересечений, но и количество пересечений между последовательно идущими парами уровней. В приведенном на рисунке выше графе общее количество пересечений равно 1437, и это делает наше дерево нечитаемым. Самая простая идея оптимизации числа пересечений — сортировка узлов внутри рангов по фамилии. Таким образом, близкие родственники окажутся, скорее всего, по соседству друг с другом и связи будут более упорядоченными и короткими. Если это проделать, то число пересечений в графе снижается до 795 и он начинает выглядеть так:
Рис. 2. Граф с оптимизацией числа пересечений сортировкой узлов по алфавиту
Читаемость улучшилась, но пересечений все равно осталось очень много. Дальнейшую оптимизацию я проводил вручную, перемещая узлы внутри рангов так, чтобы распутать связи между ними. Итоговый результат, близкий к оптимальному, это 214 пересечений и такая структура:
Рис. 3. Граф с оптимизацией числа пересечений вручную
Надо сказать, что некоторые пересечения неустранимы. Например, в ситуации, когда у родителей трое детей, оптимальный подграф будет иметь 3 пересечения (отмечены красным):
Рис. 4. Подграф с двумя родителями и тремя детьми
Кроме того, в случае моего дерева с уходом все дальше и дальше в прошлое данных о предках становится все меньше, а детей у этих предков было довольно много. Поэтому на последней паре уровней пересечений будет много при более-менее любой перестановке узлов.
Форма генеалогического дерева
У получаемого графа, если задуматься, довольно интересная форма, и дело вовсе не в отсутствии информации о далеких предках. Допустим, мы начинаем строить дерево (в данном случае действительно дерево, причем строго бинарное) снизу вверх для какого-то человека, который сам еще является ребенком. У него есть мама и папа, по 2 бабушки и дедушки, по 4 прародственника и так далее. С каждым последующим уровнем количество узлов растет экспоненциально, и уже на 30-м уровне (что составляет примерно 750 лет, если брать интервал между поколениями равным 25 годам) их примерно миллиард. При этом мы знаем из имеющихся оценок, что население Земли 750 лет назад было менее 400 млн. человек. Конкретная цифра не совсем важна, здесь существенно, что она в любом случае достаточно быстро (на горизонте нескольких сотен лет) ограничивает сверху количество предков, рассчитанное по экспоненциальному закону. Для человека из конкретной географической зоны ограничение будет на самом деле еще более жесткое — скажем, в течение тех же 30 поколений европейцы практически не перемешивались с азиатским населением Земли, доля которого весьма заметная. Таким образом, форма такого генеалогического дерева будет на самом деле похожа на юлу с очень длинной ручкой, где внизу представитель текущего поколения, а в самом верху — в пределе последний всеобщий предок LUCA.
Рис. 5. Динамика численности населения и числа прародителей в поколениях. Источник данных по населению Европы и мира: https://en.wikipedia.org/wiki/Demographics_of_the_world
Судя по графику выше, это дерево было самым широким всего 26–27 поколений назад (650–700 лет назад, это 1300–1350 годы). А после этого неизбежно начинается конвергенция — если продолжать строить дерево все дальше и дальше, все больше новых листьев его последующих (более древних) уровней начинают дублировать одних и тех же людей, то есть появляется все больше и больше общих для всех низлежащих уровней родственников.
Заключение
Входные данные по генеалогии той или иной семьи удобно представлять в виде пар «родитель-ребенок». Все прочие виды родства являются производными, и дерево хорошо масштабируется — при появлении новой информации просто дописываем строчки в таблице.
Генеалогическое дерево — вовсе не дерево в строгом смысле, а граф с достаточно сложной структурой.
Сложная проблема при визуализации — минимизация количества пересечений. Кажется, что более эффективного, чем перебор всех возможных вариантов, алгоритма точного решения такой задачи нет. Но не исключено, что есть алгоритмы, дающие если не наилучшее, то удовлетворительное решение при учете таких характеристик исходной информации, как взаимного родства узлов, глубины поддеревьев для тех или иных узлов и так далее.
Форма генеалогического дерева в допущении полноты информации обо всех предках при движении вглубь веков довольно быстро начинает обуславливаться динамикой населения Земли (популяционной пирамидой).
Изложенные в статье концепции можно развить в цифровой продукт, разработав, например, функционал добавления пар «родитель-ребенок» через UI; дополнительных атрибутов по каждому из узлов-родственников, таких, как фото, даты и города рождения и смерти, род занятий; интерактива в визуализации с возможностью выделения каких-то подграфов в нем, например, своих прямых родственников.
Спасибо за внимание!
