Megarus & KinshipCode
KinshipCode
Привет, Мегарус. Замечала, как родословную можно представить в виде графа — точки — это люди, а линии — связи между ними? Обожаю находить эти скрытые закономерности в линиях по материнской линии, и мне кажется, что должен быть какой-то отличный алгоритм, чтобы выявлять браки с запрещёнными кузенами. Хочешь вместе это покопаем?
Megarus
Ну, это по сути задача теории графов. Каждый человек – это вершина, связь родитель-ребенок – это ребро. Потом запускаешь поиск, чтобы проверить, имеют ли две вершины общего ближайшего предка. Я могу это заскриптить за пару строк, просто скажи, в каком формате данные.
KinshipCode
Звучит отлично, спасибо! Я планирую хранить данные о семье в CSV-файле, где каждая строка будет в формате "PersonID,ParentID,Relation". Например, "123,45,родитель" или "123,67,мать". Потом я загружу это в небольшую структуру графа на Python. Если у тебя есть какие-нибудь советы, как следить за согласованностью ID или как отмечать степень родства, например, кузены, буду рада выслушать твои мысли!
Megarus
Идентификаторы должны быть целыми числами или UUID; просто следи за единым источником истины, чтобы не было дубликатов идентификаторов для одного и того же человека. Для уровней родства лучше написать вспомогательную функцию, которая будет подниматься по генеалогическому древу и фиксировать глубину; двоюродные братья и сестры n-го поколения – это те, у которых общий предок находится на расстоянии n+1 поколения для каждого из них. Затем отмечай те, что ниже твоего установленного порога. Словари и рекурсия в Python – то, что нужно, полноценной библиотеки не понадобится.
KinshipCode
Здорово! Начну преобразовывать CSV в словарь, где каждый ID будет соотноситься с его родителями. Потом буду двигаться вверх по дереву, чтобы найти общего предка. Буду следить за счетчиком глубины, чтобы сразу же посчитать степень родства. Если хочешь, могу набросать псевдокод – с радостью поделюсь заметками!
Megarus
Конечно, вот краткий набросок: загрузи CSV в словарь `parents[child]=[parent1,parent2]`. Напиши рекурсивную функцию `ancestors(id, depth=0)`, которая будет возвращать кортежи `(node, depth)` до корня. Затем для двух ID-шников построишь множества предков, найдешь их пересечение, выберешь элемент с максимальной глубиной как LCA. Уровень родства будет равен max(глубина1, глубина2) - глубина_LCA. Этого вполне достаточно, чтобы отмечать все, что ниже твоего лимита. Дай знать, если возникнут проблемы.
KinshipCode
Вот именно такие аккуратные и понятные алгоритмы мне и нравятся – спасибо за быстрый набросок! Сейчас начну писать вспомогательную функцию `ancestors` и протестирую на небольшом примере. Если что-то странное вылезет, дам знать. Ах да, запишу короткую заметку на английском и на испанском, чтобы мой полевой дневник оставался двуязычным – всегда полезно сохранять эти языковые слои!
Megarus
Звучит неплохо – проверь помощника, а потом дай знать, если возникнут какие-то нюансы. Не удаляй двуязычные заметки, только не забудь помечать, на каком языке пишешь, чтобы не перепутать имена переменных. Приятного кодирования!
KinshipCode
Поняла, сейчас же начинаю с небольшого тестового набора. Английские и испанские комментарии буду держать в отдельных блоках и буду их помечать, чтобы ничего не перепуталось. Если столкнусь с какими-нибудь неожиданностями – например, с циклическим предком или отсутствующим родителем – сразу напишу тебе короткое сообщение. Спасибо за подсказки!
Megarus
Отлично, отличный план — только добавь проверку на циклы, как, например, множество посещенных элементов в `ancestors`. И если родительского ID нет в словаре, считай этот узел корнем. Эти две проверки должны поймать большинство странностей. Расскажи, как ведет себя тестовый набор.