Генерация родословного дерева на основе данных Wikipedia

В этой статье я хочу показать, как с помощью фреймворка Selenium Webdriver можно, исходя из данных Wikipedia, составить генеалогическое древо заданной персоны (например, легендарного основателя первой династии русских правителей Рюрика).

В статье будет рассказано, как определить имя персоны, вычислить ссылки на страницы детей персоны, а также будет построен алгоритм генерации генеалогического древа. Я буду использовать Java, Selenium Webdriver и Chrome. Chrome, потому что он быстрее остальных браузеров, а так как переход по урлу — самое затратное по времени операция в программе, то выбор браузера заметнее всего сказывается на времени. Можно вообще отказаться от браузера и использовать, скажем PhantomJs, но его сложнее дебажить. Поэтому я остановился на Chrome.

В первую очередь создадим тест, проверяющий, что браузер корректно запустился и что при переходе по урлу https://ru.wikipedia.org/wiki/Рюрик открывается страница с заголовком «Рюрик — Википедия»:

Создаем класс DriverHelper со статичным методом getDriver(), чтобы проект скомпилился и тест прошёл успешно:

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

Перейдем к созданию класса Person, в котором будет храниться информация о персоне, а также к созданию класса страницы персоны на Wikipedia PersonPage.

В классе Person пока будут только два поля – name и url. В качестве name будем использовать полное имя человека, без разделения на Фамилию, Имя, Отчество, т.к. большинство представителей династии не будут иметь фамилии, зато будут иметь прозвища, титулы и порядковые имена.

Url будет указывать на страницу Wikipedia, посвященную данному человеку. Создаем тест, проверяющий формирование персоны:

testGetPerson() не компилится. Нам нужно разработать страницу PersonPage, чтобы определить имя и страницу человека. Url мы определяем по url текущей страницы, а имя – по текстовому содержимому тэга с идентификатором firstHeading. Метод getPerson():

Перепрогоняем тесты – позеленели. Отдельно стоит упомянуть, почему переопределяется url, хотя он передается в качестве параметра: дело в том, что в Wikipedia одной персоне может быть посвящено несколько страниц, которые редиректятся на одну. В результате, если использовать исходные урлы, то возможно возникновение дубликатов, когда существует несколько персон с «разными» урлами, которые фактически являются одной персоной. Поэтому в качестве урла используется тот урл, на который редиректятся все остальные.

Попробуем определить детей персоны, которые имеют свои страницы в Wikipedia. Для начала напишем тест для определения детей Рюрика (точнее одного — Игоря):

Чтобы тест прошел успешно, нужно добавить на страницу PersonPage метод определения урлов детей человека:

Пока что игнорируем то, что детям могут быть не посвящены страницы в Wikipedia и поэтому они не имеют ссылок на свои страницы. Например, как в случае с детьми Владимира Ярославича (князя галицкого). Также игнорируем то, что информация о потомках может располагаться в основной области, как, например, на странице Марии Добронеги или на странице Святослава Всеволодовича (князя трубчевского).

Добавляем тесты, проверяющие корректность определения детей для персоны. Как было оговорено выше, пока предполагаем, что Владимир Ярославич (князь галицкий) и Мария Добронега детей не имели, а Владимир Святославич имел 16 детей, хотя Wikipedia утверждает, что у него было ещё 5 неизвестных по имени дочерей.

В класс Person добавим поля для уникального идентификатора персоны (int id) и списка детей персоны (List<Integer> children), в котором будут храниться идентификаторы детей. Разработаем метод добавления идентификатора ребенка в список детей персоны. Ребенок может быть добавлен в список, только если его там ещё нет.

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

Теперь перейдем к самому интересному – разработке алгоритма поиска потомков у заданной персоны. Создадим класс GenerateGenealogicalTree с методом main.

Как уже упоминалось, самое затратное по времени — переход по урлу, поэтому нужно минимизировать количество этих переходов. Для этого создадим список персон, в котором будет хранится всё родословное древо. В этом списке запомним индекс текущей персоны — той, на странице которой находимся на данный момент. Все персоны с меньшим индексом считаются «посещенными», а все с бОльшим индексом (+ текущая) — «непосещенными». После того, как был осуществлен переход на страницу текущей персоны и вычислены её основные данные, индекс увеличивается на единицу. Тем самым текущая персона попадает в разряд «посещенных». И остаётся только обойти оставшихся «непосещенных» персон. В каждый момент времени известны те персоны, страницы которых уже были просмотрены.

Наполнение родословного древа новыми «непосещенными» персонами происходит за счет добавления в конец списка детей текущей персоны. При этом добавляем только тех детей, которых ещё нет в списке, чтобы не возникали дубликаты (такая ситуация возможна, когда муж и жена — оба являются потомками родоначальника династии от разных ветвей. Примеры: муж и жена — потомки Рюрика, муж и жена — потомки Павла I).

Родословное древо считается построенным, когда не осталось «непосещенных» персон, т.е. когда индекс текущей персоны стал равным размеру родословного древа.

1. Создается основатель династии на основе заданного урла
2. Создается родословное древо на основе основателя династии
3. В цикле до тех пор, пока есть «непосещенные» персоны
4. Вычисляется персона на основе текущего урла родословного древа. Эта персона устанавливается в качестве текущей.
5. Если текущая персона не является дубликатом, то вычисляется и устанавливается список её детей. Все дети добавляются в список.
6. Если текущая персона уже встречалась среди «посещенных» персон, то она удаляется.
7. Происходит переход к следующей «непосещенной» персоне, которая принимается за «текущую».

Класс GenealogicalTree имеет три поля: List<Person> allPersons — список всех представителей родословного древа, int indexCurrentUnvisitedPerson — индекс текущей персоны в списке allPersons, а также boolean isCurrentPersonDeleted — признак того, удалена ли «текущая» персона (т.е. является ли она дубликатом).

Инициализация происходит на основе «родоначальника» династии — первой персоне, потомков которой мы ищем:

В этот момент родословное древо состоит из одной текущей «непосещенной» персоны. «Посещенных» персон нет.

Как уже упоминалось, проверка списка на наличие «непосещенных» персон осуществляется так: если индекс текущей персоны «дошел до конца», то считаем, что «непосещенных» персон не осталось.

В роли url-а родословного древа выступает url текущей персоны:

Метод setCurrentPerson заменяет текущую персону на заданную.

Изначально мы знаем о персоне только её url, который получаем со страницы родителя. Поэтому в родословное древо персона добавляется, имея только эту информацию. По сути все «непосещенные» персоны — это просто url-ы. Метод setCurrentPerson «уточняет» персону после того, как индекс «до неё добрался» и персона стала текущей.

Если устанавливаемая «уточненная» персона уже встречалась раньше (это возможно, если произошёл редирект с url-а текущей персоны на одну из встречавшихся ранее страниц), то текущая персона удаляется. После этого текущая персона помечается, как удаленная. Если заданная персона не встречается раньше, то она «замещает» текущую. При этом персона не считается удаленной.

Понятие «встречается раньше» подразумевает, что мы проверяем только «посещенные» персоны. «Непосещенные» не проверяем. Теоретически возможна ситуация, когда url текущей персоны редиректится на url, который может встречатся «позже», среди «непосещенных». Но это настолько редкая ситуация, что она не стоит того, чтобы каждый раз «пробегать» по всему массиву. В этом редком случае дубликат все равно удалится, когда до него «дойдет очередь» и индекс текущей персоны будет указывать на персону с url-ом, на который произошёл редирект.

Чтобы корректно отработал метод indexOf(Object object) необходимо в классе Person переопределить методы equals(Object object) и hashCode():

Зачем нужно постоянно проверять наличие персоны в списке? Возникновение дубликатов возможно по многим причинам:

1. Отцовство достоверно неизвестно. Как, например, в случае со Святополком Окаянным, отцом которого является либо Ярополк Святославич, либо Владимир Святославич
2. Оба родителя – потомки Рюрика от разных ветвей. Пример: Глеб Всеславич — потомок Рюрика в 8-м поколении был женат на Анастасии Ярополковне — тоже потомком Рюрика (они четвероюродные брат с сестрой).
3. Ошибки на странице: вызывает сомнение, что Всеволод Мстиславич имел сына Володаря Глебовича, родителями которого записаны другие люди, тоже принадлежащие династии Рюриковичей. Вероятнее всего, это просто опечатка в Wikipedia

Теперь рассмотрим удаление персоны из списка, когда она является дубликатом. Удаляемая персона может быть в списке детей члена родословного древа. Например, когда оба родителя являются представителями одной и той же династии, у одного родителя ссылка на одну страницу «ребенка», а у второго — на другую, которая затем редиректится на первую. Получается, что если «просто» удалить дубликат, то у второго родителя будет ссылка на несуществующую персону.

Поэтому перед удалением текущей персоны нужно заменить в списке идентификаторов детей всех «посещенных» персон её идентификатор на идентификатор найденного совпадения (у «непосещенных» детей нет).

После удаления текущая персона помечается удаленной.

В классе Person добавляем метод замены «ребенка»:

Рассмотрим добавление детей текущей персоне.

На вход мы получаем список персон, которых надо установить текущей в качестве детей. Главное отличие в поиске дубликатов состоит в том, что теперь мы будем их искать не только среди «посещенных» персон, но и среди «непосещенных», т.е. внутри всего родословного древа. Если текущая персона удалена, то выдается исключение, т.к. по сути устанавливать детей некому.

Если не удалена, то пробегаемся по списку, переданному в качестве параметра. Если ребенок уже встречается в родословном древе, то в список детей добавляется идентификатор найденного дубликата. Если ребенок не встречается в родословном древе, то в список детей добавляется его идентификатор, кроме того, сам ребенок добавляется в конец родословного древа, в список «непосещенных» персон.

Таким образом через метод setChildren() происходит «наполнение» списка.

Счетчик текущей персоны нужно обновлять, иначе родословное древо никогда не построится. Происходит это так: если текущая персона удалена, то на «её месте» уже находится следующая «непосещенная» персона, поэтому достаточно просто «снять» признак удаленной персоны с текущей. Если текущая персона не удалена, то считаем её «заполненной» всеми данными и переходим к следующей «непосещенной» персоне.

Обход осуществляется по поколениям: вначале основатель династии (0-е поколение), затем все его дети (1-е поколение) от старшего к младшему (подразумеваем, что именно в таком порядке располагаются урлы в Wikipedia), затем внуки (2-е поколение) (дети старшего сына по старшинству, затем — 2-го сына, и так до самого младшего), правнуки (3-е поколение) и так до самого последнего представителя династии.

Естественно, не забываем довести покрытие кода тестами до 100%, чтобы удостовериться, что все работает именно так, как и задумывалось. Описание тестов доступно в javadoc.

Отдельно стоит упомянуть вот о чём: класс GenealogicalTree является очень небезопасным и его легко заставить работать некорректно, если использовать вне алгоритма генерации родословного древа (вне GenerateGenealogicalTree). Единственно правильное решение в данной ситуации — перенос данного класса в качестве внутреннего приватного класса для GenerateGenealogicalTree. Но это пока не сделано для удобства тестирования алгоритма. Запускаем программу.

Первый запуск показывает, что мы имеем огромное количество данных, которые надо как-то анализировать, чтобы отсеять заведомо неверные результаты. Забегая вперед сообщу, что на 17 сентября 2017 в Wikipedia нашлось 3448 страниц прямых потомков Рюрика. Легче всего подобный объем информации обрабатывать в БД.

В первую очередь развернем локальную базу данных, которую назовем genealogicaltree. Со стандартным пользователем root без пароля. Для взаимодействия с БД будем использовать стандартную библиотеку MySQL JDBC Type 4 driver.

А дальше создаем новый класс для взаимодействия с БД и метод для сохранения родословного древа в таблице с заданным именем:

Дорабатываем сохранение результатов генерации:

Первый прогон GenerateGenealogicalTree.main() выдал много записей, беглый осмотр которых показывает наличие несуществующих и ошибочных страниц.

Разложим ошибки по категориям:

1. В список детей попал год (например, 1153 со страницы Ярослава Святославовича)
2. Нерусскоязычная статья: Аделаида Французская, дочь короля Франции Людовика VII
3. Страница «Внебрачный ребенок», появившаяся от того же Людовика VII
4. Внешние страницы наподобие этой, которые попали в список, например, от Галерана IV де Бомона
5. «Создание страницы». Например, Анна Юрьевна, дочь туровского князя Юрия Ярославича

Для начала доработаем тест testChildrenSize(), добавив в него проверку всех категории кривых ссылок:

Тест предсказуемо красный.

Теперь доработаем метод getChildrenUrl():

nameUrl — это наименование ссылки персоны, которое она имеет на странице родителя. Перепрогоняем весь комплект тестов — позеленели.

У Рюрика очень много потомков, которым посвящены русскоязычные страницы в Wikipedia, поэтому вначале прогоним программу для Михаила Фёдоровича — первого царя из рода Романовых. Запускаем, ждём окончания и анализируем результаты.

Прогон выдал 383 русскоязычные страницы потомков Михаила Федоровича (потомков с генетической точки зрения, а не с точки зрения принадлежности к роду Романовых, определяемой по мужской линии, которая прервалась ещё в 18 веке на Петре II), среди которых королева Дании, король Испании, король Нидерландов, король Швеции, и все потомки королевы Великобритании Елизаветы II, начиная с наследника британского престола принца Чарлза. Но эта информация, конечно, имеет второстепенное значение к исходной задаче.

Проанализируем результаты с точки зрения достоверности данных. Прогон выдал несколько ошибочных записей:

1. Две персоны с именем Владимир Александрович и две персоны с именем Фризо Оранско-Нассауский
2. Три персоны с необычным именем Дети Алексея Михайловича, две с — Дети Ивана V, один с — Дети Петра I и ещё три- с Дети Михаила Фёдоровича

Первое, что бросается в глаза — это то, что данные представители династии потомков после себя не оставили, т.к. умерли маленькими детьми (за исключением, конечно же, дочерей Фризо Оранско-Нассауского, которые ещё не успели вырасти) Поэтому можно смело дорабатывать метод getChildrenUrl(), возвращая пустой список, если текущий url имеет якорь. Это необходимо сделать, чтобы персоне с «якорем» в качестве детей не установились дети её родителя, т.е. собственные братья и сестры, как в первом случае ошибочных записей.

Добавляем новый тест, проверяющий, что персона с урлом, содержащим якорь, не имеет детей:

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

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

В большинстве подобных случаев имя персоны можно вычислить по «якорю»: имя — это текстовое содержимое тэга с идентификатором, равным значению «якоря». Доработаем метод getName():

Если текущий url содержит «якорь», то необходимо проверить существование на странице элемента с идентификатором, равным «якорю». Его может не существовать, как в случае с Натальей — дочерью Петра I. На странице Петра ссылка содержит уже несуществующий «якорь», который не соответствует «якорю» Натальи.

Также необходимо убедиться, что тэг с идентификатором «якоря» содержит непустой текст и вернуть наименование страницы в противном случае. Иначе, как, например, в ситуации с Демьяном Глебовичем, определится пустое имя и программа вылетит с исключением. Тесты опять позеленели.

Осталось проблема: имя Александра, старшего сына Владимира Александровича, определяется как «Семья». Что с этим делать?!

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

Конечно, не забываем покрыть тестами весь доработанный код.

Результатом доработки является то, что теперь у персоны есть два «имени», одно из которых уж точно «должно быть информативным». Исключением, по понятным причинам, является родоначальник династии, для которого nameUrl может быть любым (присвоим значение "" для определённости).

Перепрогоняем программу для Романовых и сверяем данные с теми, что были собраны до рефакторинга.

Вот так теперь выглядят урлы с якорями: id name children url urlName 8 Пелагея [] ссылка Пелагея 9 Марфа [] ссылка Марфа 10 Софья [] ссылка Софья 15 Анна [] ссылка Анна 23 Евдокия (младшая) [] ссылка Евдокия 26 Феодора [] ссылка Феодора 28 Мария [] ссылка Мария 29 Феодосия [] ссылка Феодосия 36 Дети Петра I [] ссылка Наталья 133 Семья [] ссылка Александр 360 Брак и дети [] ссылка Луана Оранско-Нассауская Добавление наименования ссылки не прошло бесследно. Прогон программы для Рюрика неожиданно вылетел с исключением о нарушении инструкции insert на Генрихе II (короле Наварры) из-за того, что nameUrl содержит значение с апострофом — «Генрих II д'Альбре». Доработаем методы setName и setNameUrl в классе Person, сохраняя заданное значение без апострофов.

Напомню, что в Wikipedia нашлось около трех с половиной тысяч потомков Рюрика. Если выводить эту информацию в виде таблицы, то получится очень большая страница, которую устанешь прокручивать. Было бы интересно не только видеть всю табличку, но иметь ещё возможность выделить связь заданного представителя с родоначальником династии (т.е. выделить всех предков заданного представителя вплоть до родоначальника). А также знать, каким по счету поколением он является.

Чтобы легче было реализовывать эту новую функциональность, добавим в класс Person поля для номера поколения и списка родителей (чтобы легче было построить возрастающую связь):

Родитель в большинстве случаев будет один, но возможны ситуации, когда оба родителя потомки родоначальника династии от разных ветвей и тогда их будет двое. Выше даже был приведен пример ошибки, когда сразу трое «являются» родителями одного и того же человека (первый, второй, третий, их «общий» ребенок — и все Рюриковичи). Конечно, физиологически это невозможно, получается, как в анектоде, но, к сожалению, автоматически определить, кто их них «лишний» невозможно, поэтому придется сохранять всех.

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

Что касается номера колена, то оно устанавливается только один раз от первого родителя. В тот момент, когда появляется второй родитель, ссылающийся на ребенка, номер поколения уже не обновляется. Т.к. обход родословного древа происходит по поколениям, то, очевидно, что номер поколения НЕпервого родителя будет равен или больше, чем номер колена первого родителя, а значит быстрее всего построить связь через «первых родителей».

Устанавливать номер поколения и идентификатор родителя будем в методе setChildren(List<Person> children) класса GenerateGenealogicalTree:

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

Пришло время сформировать несколько родословных деревьев и посмотреть результаты: Адам — первый человек на Земле Чингисхан — величайший завоеватель в истории Романовы Рюриковичи (долго открывается — 3452 персоны).

Пояснение к страницам:

а) при нажатии на имя открывается страница персоны на Wikipedia б) при нажатии на № открывается страница связи заданной персоны с родоначальником. Например, вот страница, доказывающая, что королева Великобритании Елизавета II является потомком Рюрика в 29 поколении. в) при нажатии на идентификаторы в полях родителей и детей страница прокручивается на строку с этой персоной.

Результаты показывают, что, например, последний российский император Николай II был потомком Рюрика в 28 поколении. Более того, все российские императоры, начиная с Петра III и Екатерины II были потомками Рюрика от разных ветвей.

Для визуализации данных в виде дерева я использовал библиотеку JavaScript InfoVis Toolkit. Ссылки на родословные древа в виде дерева, а не списка: Адам Чингисхан Романовы Рюриковичи