Всем привет. Разумеется, это шутка — я своих родственников очень люблю, уважаю и никоим образом их не притеснял и не планирую. Более точная формулировка — отсортировал в целях построения генеалогического древа. Об алгоритме построения, сортировки, визуализации фамильного древа и будет эта статья.
Собственно, с чего всё началось. Мой папа и я имели огромное желание создать генеалогическое древо рода. Меня, конечно, больше влекла визуальная составляющая — знаете, все эти средневековые полотна с некрасивыми мужчинами, бледными дамами в париках, золотые рамки, даты жизни римскими цифрами, деревья с узловатыми ветвями и зелёными листьями и т. д.? Вот это вот всё. Папа кропотливо собирал какие-то бумаги, обзванивал родных, вёл записи.
Однажды я пообещал ему нарисовать древо на компьютере, т. к. попытки набросать его вручную на куске ватмана не увенчались успехом — в этот момент я понял, что герольды, живущие при дворе, не зря кушали свой хлебушек. Было несколько подходов: попытки освоить специализированный софт, потом что-то написать своё, но всё время результат был недостижим. Время шло — папу унёс ковид, а обещание так и осталось висеть на моей совести.
Всё изменилось, когда пришла пора моей дочке писать диплом. Мы сразу отмели все темы из ассортимента вуза и заявили собственную — построение генеалогического древа. Отступать стало некуда.
Для начала немного погрузимся в специфику задачи — рекомендую несколько местных статей:
краткий обзор софта «Программы для генеалогического дерева» и пара реализаций «Bonsai: фамильный вики-движок», «Как я древо семьи строил».
Интерфейсная часть с реализацией ведения персон в базе данных вещь, на мой взгляд, довольно тривиальная и была реализована весьма быстро, демонстрировать здесь не вижу смысла.
Алгоритм визуализации древа — вот что самое интересное и заставляет серьёзно загрузить голову. Про него и буду рассказывать. Для нетерпеливых сразу скажу, что исходники пока не выкладываем, но есть демонстрационный сайт, куда можно загрузить своё древо в формате GEDCOM — ссылка ближе к концу статьи.
Принципы построения древа неплохо описаны в статье «Как я древо семьи строил», мы приняли их почти все, за исключением различных вариантов имбридинга — наше фамильное древо пока этим не отягощено.
И хочу сразу уведомить — генеалогия это в чистом виде биология с наложением различных видов семейных связей: официальный (государственный), церковный, гражданский браки. И именно биология жёстко указывает, что дети рождаются только у мальчика и девочки, а также не существует других гендеров кроме «М» и «Ж».
▍ Подглядываем за конкурентами. Неудачные попытки промышленного шпионажа.
Как говорила одна моя хорошая знакомая: главное в решении задачи — это найти её полный аналог. План следующий: ищем в интернетах и интегрируем в проект готовый компонент, а сэкономленное время посвящаем просмотру сериальчиков.
Посмотрели источник «Bonsai: фамильный вики-движок» — описание толковое, в конце есть ссылка на демосайт с практически нулевой ценностью. Я серьёзно — расписать суперкрутой алгоритм, но не дать возможности проверить его работу на более-менее реальном объёме данных? Импорт из GEDCOM реализовать несложно, а вводить вручную своё древо (почти 300 персон) мы не решились.
Источник «Как я древо семьи строил». Хорошо описаны принципы построения и алгоритм. Есть демка с довольно большим объёмом данных. Но! В визуализации месиво и реализация отходит от описанных правил построения. Видимо, сам алгоритм некорректный или не полностью реализован. Для очистки совести сгенерировали и загрузили свои данные, итог — твёрдое нет. Древо получилось не планарное, навигация неудобная, часть родственников потеряли связи, часть и вовсе испарилась. Вдобавок можно двигать людей по вертикали.
Вспомнил я, что когда-то пробовал вести древо на сайте genway.ru и он даже понравился своим интерактивным методом построения древа. Сразу проблема — хоть сайт и живой, но всё реализовано на флеше. Достал свой древний «атомный» ноут с виндой XP и прорвался-таки туда! Стащил с него все флешевские файлы, пихнул в декомпилятор ныне уже мёртвого языка. Результат весьма недурственный — в наличии имена переменных, названия функций, даже комментарии. Попытались погрузиться, но в итоге отодвинули в сторону. Некромансеры из нас так себе.
Есть ещё один сайт, свеженький, на JavaScript, и ввод совсем как на генвее. Терзают смутные сомнения, что автор генвея рецидивист и взялся за старое. Но, помимо отсутствия импорта GEDCOM, у него есть фатальный недостаток — абсолютно всё там реализовано на JavaScript. Объём большой, мы к этому не готовы. В общем, тут тоже тупик.
Параллельно отсмотрели ещё много всяких библиотек, но уже не помню причин, по которым их не приняли «в производство». Но причины были весомые.
▍ Приступаем к собственной реализации
«Лайтовенькие» на первый взгляд варианты отвалились, придётся делать всё самим. Сразу прикинули, что без JavaScript не обойтись, посему будем привлекать библиотеку vis.js. Выбор был обусловлен наличием положительного опыта её использования в одном pet-проекте. Не исключено, что если бы выбрали другую, аналогичную библиотеку, статья получилась бы значительно короче :). Как пользоваться vis.js я решил тут не показывать — на сайте есть огромное количество демонстрационных примеров.
Vis.js очень хорошо умеет рисовать графы, и самое главное — иерархические. Прикинули быстренько: чтобы получить нашу эталонную картинку, потребуется завести ещё одну ноду — «семья». Эта концепция позволяет не потерять родственников, не имеющих детей (прямых кровных связей). Выглядит это примерно вот так:
Как решили, так и сделали. Пока без программирования, просто в html вставили персоны, граф настроен на иерархию. На одной семье результат отличный (картинка выше), только линии связей «из коробки» не совсем то, что нам хочется, но подобрали более-менее приемлемые варианты, тюнинг на потом отложим.
Шустро написали на PHP скрипт, генерирующий страничку на весь объём базы — это примерно 300 человек. Не забываем создавать парную безымянную персону для матерей/отцов-одиночек.
Результат удручающий — система пытается построить дерево, где из одной вершины идут ветви, а нам надо, чтобы вершин было две (термин «генеалогическое древо» вводит в заблуждение, т. к. реально это «генеалогический граф»). Но зато древо получилось с прикольным «желейным» поведением при перемещении нод.
Пробуем поиграть со штатными методами сортировки — sortMethod и shakeTowards — вроде как добились того, что родителей двое, всё ещё не то. Системе просто невозможно объяснить, что между родителем и ребёнком должно быть ровно два уровня (с учётом семьи). Пытается выровнять по верхнему или нижнему краю — внуки оказываются на одном уровне с прапрадедушкой и наоборот, плюс неоптимальные перекрёстные связи.
Это просто кошмар — не фамильное древо благопристойной семьи, а карта преступных связей на стене детектива.
Ладно, у vis.js есть возможность вручную прописать уровни, и мы ей воспользуемся.
▍ Сортировка персон
Мы манипулируем двумя видами объектов: персона и семья. Объект персона имеет связь с семьёй, где она родилась, и связи с семьями, где она является одним из родителей. Соответственно, объект семья имеет связь «папа» к персоне отцу и связь «мама» к матери. Также объект семья может иметь связи к каждому ребёнку, рождённому в данной семье. Написал может, т. к. мы отображаем и просто супружеские пары, без детей.
Алгоритм несложный, рекурсивный — всем персонам устанавливаем поколение (далее для простоты — уровень) 0, а семьям 1. Выбираем одного человека и присваиваем ему уровень 1. От этого человека рекурсивно движемся по семейным связям — ушли в родительскую связь и данной семье присвоили уровень на единицу меньше (0), ушли в связи, где он родитель — в данных семьях уровень +1 относительно этого человека. Аналогично с семьями — уходим к маме или папе — им уровень на 1 меньше, чем уровень данной семьи, провалились к детям — уровень повышается.
Чтобы рекурсия завершилась, не заглядываем туда, откуда пришли. Кроме того, учитываем, что непросмотренные люди имеют уровень 0, а семьи 1. В итоге у нас получится, что люди разместились на нечётных уровнях, а семьи на чётных.
Уже намного лучше. Только вот в этом месиве по-прежнему не разобрать где свои, а где другие свои.
Начнём зачистку. Навскидку сразу можно убрать со схемы объект семья. Ставим атрибут невидимости и снова генерируем древо. Вроде и стало чище, а на самом деле кошмар — мы можем двигать персоны, а семьи остаются на месте. Они невидимы во всех смыслах, их и мышкой не захватить. Ок, сделаем их видимыми, но размером 1 или 2 или 3. Вроде чище, но тоже нехорошо, а всё потому, что у нас осталась штатная сортировка в пределах уровня. Вернее отсутствие сортировки. Автоматом ничего не распутывается.
Дело в том, что в vis.js реализован движок hierarchicalRepulsion, который работает примерно так (утрированно) — каждая нода имеет некоторую гравитацию, которая притягивает их всех в центр друг к другу, но вместе с тем они имеют одинаковый заряд, который не даёт им сближаться слишком близко (они как бы отталкиваются). На определённом расстоянии гравитация и силы отталкивания уравновешивают друг друга, и положение нод стабилизируется.
Также имеются связи между некоторыми нодами, которые представляют собой своего рода пружинки. Поведение аналогичное, как между несвязанными нодами, только более сильное и притяжение с расстоянием увеличивается. Всё это считается итеративно, позволяя получать шикарный желейный эффект при различных манипуляциях с древом.
Ну и есть ещё некоторые нюансы — например, это ноды, которые не участвуют в симуляции. Они либо имеют атрибут с запретом на физическую симуляцию, либо являются невидимыми объектами.
Всё это худо-бедно работает на плоскости, в двумерном пространстве, но когда ноды находятся на прямой, разойтись они не могут. Подкрутка коэффициентов ничего не даст — пробовали. Также ничего не даст добавление дополнительных связей между родителями, между родителем и ребёнком. Всё потому, что в иерархическом графе ноды могут двигаться только по горизонтали. И сила отталкивания одноимённых зарядов между нодами довольно сильная, даже пружинка не может её преодолеть. И даже две, три пружинки :) Вот и получается, что если vis.js поставил между мамой и папой условного троюродного дядю, то им не быть больше вместе. Это печально. Воссоединить их может только пользователь, приложив значительные усилия к движению мыши (если можно так выразиться), захватив ноду и резко перемещая её вправо или влево.
▍ Рисуем красивое
Ладно, оставим пока всё как есть, переключимся на визуализацию. У нас есть объекты родители, дети и семья, которых мы хотим видеть так, а пока штатно можно получить вот так, и навскидку надеемся сделать вот так (нарисовано вручную в графическом редакторе):
Для наглядности связь между двумя нодами (семья и сын) изобразил зелёным цветом. Все остальные связи идентичны.
Т. е. нам надо добавить один незамысловатый вид связи между нодами. Скачиваем с гитхаба исходники vis.js, смотрим. Первая мысль — надо закачать обратно. Не готовы мы лопатить такие объёмы!
В который раз изучаем возможности vis.js. И тут в примерах глаз цепляется за обработчики beforeDrawing/afterDrawing. Суть идеи — штатные связи-пружинки оставляем, но только не показываем. Необходимые видимые связи отрисуем в функции beforeDrawing. Читаем, как добраться до нод и их атрибутов через api DataSet, и в итоге рожаем такую функцию:
network.on("beforeDrawing", function (ctx) {
ctx.strokeStyle = "#ff3333";
ctx.lineWidth = 1;
ctx.beginPath();
ctx.moveTo(0, 0);
for(const Node1 of nodes.get()) {
var Pos1 = network.getPositions([Node1.id])[Node1.id];
for(const Node2 of network.getConnectedNodes(Node1.id, "to")) {
var Pos2 = network.getPositions([Node2])[Node2];
ctx.moveTo(Pos1.x, Pos1.y);
ctx.lineTo(Pos1.x, Pos1.y + 50);
ctx.lineTo(Pos2.x, Pos1.y + 50);
ctx.lineTo(Pos2.x, Pos2.y);
}
}
ctx.moveTo(0, 0);
ctx.closePath();
ctx.stroke();
});
И результат её применения к тестовой семье (оставил прямые связи между нодами для наглядности) и ко всему древу.
Вроде всё как хотели, но на полном объёме результат ещё хуже. Раньше хоть по плавным изгибам можно было предположить направление связи, а сейчас стало намного запутаннее — все горизонтальные связи слились в одну линию, вертикальные заходят под прямым углом.
И вот примерно на этом этапе нам пришло одно очень важное понимание. Древо должно строиться не по всему объёму людей в базе, а только по тем персонам, которые имеют «кровные связи» с конкретным человеком. Это логично и соответствует биологическому понятию родства, но почему-то в источниках по построению деревьев мне данная мысль в чистом виде не встречалась. Возможно, тривиальные вещи просто считается стыдным разжёвывать?
Реализация простая до безобразия. Вспоминаем рекурсивный алгоритм распределения людей по уровням: когда мы зашли в семью со стороны одного из родителей, то его супругу мы присваиваем уровень и отобразим на схеме, но дальше к его родительской семье не идём и все они остаются на 0-м уровне. Затем, при генерации данных для vis.js мы пропустим персоны с уровнем 0. Однако пользователю необходимо показать, что за этим человеком есть ещё родители/семья/клан, поэтому здесь можно добавить на картинку какой-нибудь атрибут, например веточку (стрелку, звёздочку).
В данном случае древо было построено для человека, который был выбран самым первым узлом при расчёте уровня. Несложно в готовом графе vis.js сделать выбор мышкой произвольного узла (персоны) и произвести перестроение древа для данного человека. Сделали.
Вернёмся опять к визуализации (если обратили внимание — пишу в порядке хронологии, выглядит сумбурно и бессистемно, придётся потерпеть :) Типичная ситуация — родители слева, семья справа, дети слева. У другой семьи может быть аналогичная, но зеркальная раскладка.
Как мы уже понимаем, семьи автоматически между собой не поменяются местами, а ведь они у нас являются ключевым объектом при построении связей. А что, если отойти от концепции рисования связей между нодами, а отрисовывать связи в пределах семьи? Для ключевой точки «А» высчитываем координату х между родителями, координата у берётся от объекта семья. Немного отступов туда, сюда и вот финальный результат (функцию не привожу, только картинка):
Для наглядности оставлено отображение связей с семьёй, справа они скрыты атрибутом hidden.
Ещё разок посмотрим на схему – явно лишний объект «семья». Теперь он не имеет визуальных связей и вообще может находиться в неизвестных местах. Возникла мысль — а может ну её нафиг, эту семью? Я имею в виду не свободу нравов, а ноду, через которую идёт связь детей с родителями.
Вот взять и сделать таким образом:
Налицо сплошные плюсы — связи между супругами явные, детишки тянут свои ручонки прямо к папе и маме, а полосочки мы и так мимо семьи рисуем.
Посмотрели код, прикинули, откуда что берётся — вот и не получится от семьи избавиться. Нужна семья как источник данных, но как узел древа лишняя. И мы подобный подход отметили как недостаток при рассмотрении алгоритма статьи «Как я древо семьи строил»
Значит будем информацию по семьям отдавать отдельно от данных vis.js. После очередной переделки всё стало даже быстрее бегать — это вызовы DataSet отбирали изрядное количество ресурсов. Из дополнительных плюшек — бездетные семьи отображаем прямыми линками без спуска на уровень ниже.
▍ Опять сортируем
С визуализацией закончили (ну почти — есть замечания, но об этом позже), пора опять возвращаться к сортировке людей на уровне. Мы уже внутренне смирились, что придётся делать её самостоятельно. И тут возникает очередной вопрос — нафига нам этот vis.js? Ах да, это клёвое желе %)
Итак, делаем простейшую сортировку вручную и наслаждаемся результатом. Это мы сначала так думали. На самом деле хоть засортируйся — узлы будут идти в случайном порядке. И только путём невероятных поисков на форумах удалось выяснить (не одни мы по этим граблям прошлись) – надо использовать версию vis.js 4.8.1. Дескать, работает по-человечески, отображает узлы в порядке появления слева направо. Нашли, скачали, вставили. Всё нормально — порядок наш сохранён, прочая функциональность на месте.
Далее пишем функцию сортировки. Опять некорректное название — это функция сравнения двух объектов, которую использует штатная библиотечная функция сортировки. Сортировка осуществляется на нашем бэкенде, поэтому пишем на PHP.
Кратенько внутреннюю модель данных я упоминал. Что нам надо знать, чтобы сделать эту функцию сравнения:
- Т. к. сортируем начиная с предков, то уровни выше уже отсортированы. Доступ к объектам верхнего уровня мы имеем через связь с объектом типа семья. Через эту связь мы можем разместить детей под родителями.
- Новые люди (без родителей) появляются максимально справа. Это хорошо на первом этапе, но есть планы переделать.
- Объект семья сортируется крайне просто — сортируем в порядке следования глав (отцов) семейств.
- Супругов размещаем рядышком. Это значит, что мужчину придвигаем на ближайший к семье женщины край, а женщина покидает семью и становится рядом с мужем, связи с семьёй не разрываем. Такова её женская доля :) Всё это доступно через связь с семьёй (семьями) нижнего уровня.
- Если супруг без родителей, то рисуется рядом со второй половинкой.
Вот коротенько все критерии сортировки, которые умещаются на один экранчик кода.
Финал близко, на несложных схемах выглядит шикарно. Осталась одна проблема — горизонтальная полоса на насыщенных уровнях. Скриншот не привожу, т. к. эти артефакты отлично видно на скриншоте, где впервые применён собственный метод отрисовки связей. Лечится довольно просто — где мы формируем псевдообъект «семья» для нашего фронтенда, нам в каждую семью необходимо добавить небольшой атрибут — смещение. Это небольшое смещение по оси ординат, которое мы будем добавлять, когда рисуем горизонтальные линии связей в семьях.
Мы у себя считаем его следующим образом — после сортировки уровня с семьями делается ещё один проход, и семье добавляется смещение, равное количеству детей, умноженное на 3 (пикселя). Если смещение предыдущей семьи такое-же, то накидываем ещё 3. Визуально семьи расходятся по уровню, становится очень симпатично.
Сортировка есть, она работает, но не идеально. По прежнему есть места, которые после ручной оптимизации выглядят намного лучше. Основной источник проблем — критерий сортировки номер 2. Тут я вижу только формирование оценки упорядоченности, например, количество внутренних пересечений связей между семьями, и далее перебором мест размещения новой персоны искать минимальное значение этого показателя.
▍ Демо
Демонстрационную версию, вырванную из диплома, я разместил на серверочке от RUVDS. Находится оно здесь — gtree2. Можно глянуть наше обезличенное древо либо загрузить своё в формате GEDCOM. Загруженные файлы хранятся сутки, потом крон их удаляет. Хост слабенький, но буду иногда заглядывать и поднимать.
Что там можно с этим уже делать:
- загружать и визуализировать собственное древо в формате GEDCOM;
- скрывать/отображать связи между родителями и детьми;
- отключать/включать «физику». При отключении удобно двигать людей вручную в пределах уровня, а затем опять автоматически выравнивать их относительно друг друга;
- дважды кликнув по персоне перестроить древо для этой персоны.
▍ Разглядываем сторонние деревья
У кого нет собственных деревьев в формате GEDCOM, могут поискать их в интернете. Ниже привожу ссылки.
Здесь можно скачать древо «The English and British Kings and Queens» и древо «The Kennedy Family of the United States».
Древо английской короны ужасно. Большое в плане глубины поколений. Почему-то в некоторых записях FAM неполных семей, мужчины обозначены как WIFE, а женщины как HUSB. Кривое древо потребовало для себя корявый код :(
Древо Kennedy — ничего примечательного. Персон немного, требует минимум ручного вмешательства.
Вот ещё один ресурс с некоторым количеством доступных GEDCOM файлов.
Royal92.ged европейские монархи — у меня строится очень долго. Само древо большое — вероятно, восходит к неандертальцам. Тут наши алгоритмы сдаются, т. к. царствующих особ невероятно много и у них были весьма популярны близкородственные связи.
Shakespeare — простенькое древо. Здесь я узнал, что Вильям был женат и у него было трое детей.
Bronte — древо писательниц Бронте. Тут мне потребовалось беглое обращение к Википедии. Само древо скромное.
Pres2020 — «An excellent collection of the presidents of the US, with their ancestors and descendants». Ещё одно гадкое древо. Вернее не древо, а набор не связанных между собой деревьев. Чтобы добраться до какого-либо президента, нужно заглянуть в GED-файл и узнать его идентификатор. Далее вбиваем в URL в таком виде http://176.119.159.132/gtree2/index.php?root=@I0006@. Ну и для пробы Кеннеди — @I1509@ (можно сравнить с предыдущим ресурсом), Рузвельт — @I1466@, Обама — @I2194@, Трамп — @I2185@. А вот Байден, ака «самоходный дед», пока отсутствует — не ищите.
Скриншоты приводить не стал — проще скачать самостоятельно и смотреть на сайте.
▍ Финал
Дочка диплом защитила на «отлично» и у нашего рода появилось полноценное фамильное древо. Возможно, мы созреем и соберём общедоступный релиз для самостоятельного развёртывания на персональных ресурсах, но это не точно :)
Автор:
alef13
