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 нет в словаре, считай этот узел корнем. Эти две проверки должны поймать большинство странностей. Расскажи, как ведет себя тестовый набор.
KinshipCode
Добавила защиту посещенных множеств и резервный вариант с корнем в `ancestors`. Проверила тестовый набор на небольшой семье из шести узлов. Алгоритм правильно определил ЛСН и уровень родства для каждой пары — никаких циклов, нет пропущенных родителей. Пока всё отлично! Если что-то странное вылезет, когда буду загружать полные данные, сообщу.
Megarus
Отличная работа, быстро с ошибками разобралась! Только следи за размером данных, ладно? Если память закончится, просто раздели на части или используй потоковую обработку. Если понадобится, могу быстро подшаманить.
KinshipCode
Спасибо! Буду следить за размером датасета и буду стримить его, если станет слишком большим. Просто дай знать, если понадобится быстрая оптимизация или возникнут какие-то другие проблемы. Приятного кодирования!
Megarus
Удачи с взломом — пиши, если график начнет вести себя как сумасшедший ИИ.
KinshipCode
Спасибо! Буду следить за порядком с заметками – английский для кода, испанский для полевых наблюдений – и внимательно отслеживать использование памяти. Если график начнёт расти неконтролируемо, я его разделю на части или буду стримить, и дам знать, если что-то покажется мне странным, как поведение искусственного интеллекта. Приятного анализа!