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

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

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

@BeforeClass
public static void Start() {
    driver = DriverHelper.getDriver();
}

@Test
public void testGetDriver() {
    driver.navigate().to("https://ru.wikipedia.org/wiki/%D0%A0%D1%8E%D1%80%D0%B8%D0%BA");
    assertTrue(driver.getTitle().equals("Рюрик — Википедия"));
}

@AfterClass
public static void Stop() {
    driver.quit();
}

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

public final class DriverHelper{
    private static final int TIMEOUT = 30;

    public static WebDriver getDriver() {
        WebDriver driver = new ChromeDriver();
        driver.manage().window().maximize();
        driver.manage().timeouts().implicitlyWait(TIMEOUT, TimeUnit.SECONDS);
        return driver;
    }
}

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

Создание класса Person

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

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

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

@Test
public void testGetPerson() throws Exception {
    PersonPage page = new PersonPage(driver);
    Person person = page.getPerson("https://ru.wikipedia.org/wiki/Владимир_Александрович");
    assertTrue(person.getName().equals("Владимир Александрович"));
    assertTrue(person.getUrl().equals(
        "https://ru.wikipedia.org/wiki/
        %D0%92%D0%BB%D0%B0%D0%B4%D0%B8%D0%BC%D0%B8%D1%80_
        %D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87"));
}

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

public Person getPerson(String url) throws MalformedURLException {
    driver.navigate().to(url);

    String name = getName();

    Person person = new Person(driver.getCurrentUrl());
    person.setName(name);
    return person;
}

private String getName() throws MalformedURLException {
    String namePage = driver.findElement(By.cssSelector("#firstHeading")).getText();
    return namePage;
}

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

Например: страница https://ru.wikipedia.org/wiki/Ярослав_Мудрый перенаправляется на https://ru.wikipedia.org/wiki/Ярослав_Владимирович_Мудрый, а страница https://ru.wikipedia.org/wiki/Андрей_Боголюбский — на https://ru.wikipedia.org/wiki/Андрей_Юрьевич_Боголюбский

Определение детей персоны

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

@Test
public void testGetChildrenUrl() throws Exception {
    driver.navigate().to("https://ru.wikipedia.org/wiki/Рюрик");
    PersonPage page = new PersonPage(driver);
    List<Person> children = page.getChildrenUrl();
    assertTrue(children.size() == 1);
    Person person = children.get(0);
    assertTrue(person.getUrl().equals("https://ru.wikipedia.org/wiki/
        %D0%98%D0%B3%D0%BE%D1%80%D1%8C_
        %D0%A0%D1%8E%D1%80%D0%B8%D0%BA%D0%BE%D0%B2%D0%B8%D1%87"));
}

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

public List<Person> getChildrenUrl() throws MalformedURLException {
    List<WebElement> childrenLinks = driver.findElements(
        By.xpath("//table[contains(@class, 'infobox')]//tr[th[.='Дети:']]//a"));
    List<Person> children = new ArrayList<Person>();
    for (WebElement link : childrenLinks) {
        Person person = new Person(link.getAttribute("href"));
        children.add(person);
    }
    return children;
}

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

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

@Test
public void testChildrenSize() throws Exception {
    driver.navigate().to("https://ru.wikipedia.org/wiki/Рюрик");
    PersonPage page = new PersonPage(driver);
    List<String> children = page.getChildrenUrl();
    assertTrue(children.size() == 1);

    driver.navigate().to("https://ru.wikipedia.org/wiki/Владимир_Святославич");
    children = page.getChildrenUrl();
    assertTrue(children.size() == 16);

    driver.navigate().to("https://ru.wikipedia.org/wiki/Владимир_Ярославич_(князь_галицкий)");
    children = page.getChildrenUrl();
    assertTrue(children.size() == 0);

    driver.navigate().to("https://ru.wikipedia.org/wiki/Мария_Добронега");
    children = page.getChildrenUrl();
    assertTrue(children.size() == 0);
}

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

public void setChild(int childId) {
    if (!children.contains(childId)) {
        children.add(childId);
    }
}

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

Алгоритм поиска потомков

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

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

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

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

Алгоритм такой:

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

Код алгоритма:

public final class GenerateGenealogicalTree {
    public static void main(String[] args) throws Exception {
        String url = getUrl(args);
        GenealogicalTree tree = getGenealogicalTreeByUrl(url);
        saveResultAndQuit(tree);
    }

    public static GenealogicalTree getGenealogicalTreeByUrl(String url) throws MalformedURLException {
        WebDriver driver = DriverHelper.getDriver();
        Person person = new Person(url);
        GenealogicalTree tree = new GenealogicalTree(person);
        PersonPage page = new PersonPage(driver);
        while (tree.hasUnvisitingPerson()) {
            String currentUrl = tree.getCurrentUrl();
            Person currentPerson = page.getPerson(currentUrl);
            tree.setCurrentPerson(currentPerson);
            if (!tree.isCurrentPersonDeleted()) {
                List<Person> children = page.getChildrenUrl();
                tree.setChildren(children);
             }
             tree.updatingCurrentPerson();
        }
        driver.quit();
        return tree;
    }
}

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

public final class GenealogicalTree {
    private List<Person> allPersons;
    private int indexCurrentUnvisitedPerson;
    private boolean isCurrentPersonDeleted;
}

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

public GenealogicalTree(Person person) {
    if (person == null) {
        throw new IllegalArgumentException("Укажите непустого основателя династии");
    }
    allPersons = new ArrayList<Person>();
    allPersons.add(person);
    indexCurrentUnvisitedPerson = 0;
    isCurrentPersonDeleted = false;
}

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

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

public boolean hasUnvisitingPerson() {
    return indexCurrentUnvisitedPerson < allPersons.size();
}

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

public String getCurrentUrl() {
    return allPersons.get(indexCurrentUnvisitedPerson).getUrl();
}

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

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

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

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

public void setCurrentPerson(Person currentPerson) {
    int indexDuplicate = allPersons.indexOf(currentPerson);
    if ((0 <= indexDuplicate) && (indexDuplicate < indexCurrentUnvisitedPerson)) {
        removePerson(indexDuplicate);
    } else {
        allPersons.get(indexCurrentUnvisitedPerson).copyMainData(currentPerson);
        isCurrentPersonDeleted = false;
    }
}

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

@Override
public boolean equals(Object object) {
    if ((object == null) || (!(object instanceof Person))) {
        return false;
    }

    Person person = (Person) object;
    return this.url.equals(person.url);
}

@Override
public int hashCode() {
    return this.url.hashCode();
}

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

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

Если эти дубликаты не устранить, то они породят новые повторения, т.к. по всем потомкам дубликатов обход будет производится два раза, а то и три (в случае с Володарем Глебовичем).

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

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

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

private void removePerson(int indexDuplicate) {
    int idRemovedPerson = allPersons.get(indexCurrentUnvisitedPerson).getId();
    int idDuplicate = allPersons.get(indexDuplicate).getId();
    for (int i = 0; i < indexCurrentUnvisitedPerson; i++) {
        Person person = allPersons.get(i);
        person.replaceChild(idRemovedPerson, idDuplicate);
    }
    allPersons.remove(indexCurrentUnvisitedPerson);
    isCurrentPersonDeleted = true;
}

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

public void replaceChild(int oldId, int newId) {
    if (oldId == newId) {
        return;
    }
    if (!children.contains(oldId)) {
        return;
    }
    children.remove((Object) oldId);
    setChild(newId);
}

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

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

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

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

public void setChildren(List<Person> children) {
    if (isCurrentPersonDeleted) {
        throw new IllegalArgumentException(
            "Нельзя установить детей удаленной персоне. Текущая персона уже другая");
    }

    for (Person person : children) {
        int index = allPersons.indexOf(person);
        int id;
        if (index >= 0) {
            id = allPersons.get(index).getId();
        } else {
            allPersons.add(person);
            id = person.getId();
        }
        allPersons.get(indexCurrentUnvisitedPerson).setChild(id);
    }
}

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

public void updatingCurrentPerson() {
    if (isCurrentPersonDeleted) {
        isCurrentPersonDeleted = false;
    } else {
        indexCurrentUnvisitedPerson++;
    }
}

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

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

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

Логирование результатов в БД

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

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

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

public class MySqlHelper {
    private static final String url = "jdbc:mysql://localhost:3306/genealogicaltree" 
        + "?serverTimezone=UTC&useUnicode=yes&characterEncoding=UTF-8";
    private static final String user = "root";
    private static final String password = "";

    private static Connection connection;
    private static Statement statement;
    private static ResultSet resultSet;

    public static void saveTree(String tableName, List<Person> tree) throws MalformedURLException {
        try {
            connection = DriverManager.getConnection(url, user, password);
            statement = connection.createStatement();

            String table = createTable(tableName);
            statement.executeUpdate(table);

            for (Person person : tree) {
                String insert = insertPerson(tableName, person);
                statement.executeUpdate(insert);
            }
        } catch (SQLException sqlEx) {
            sqlEx.printStackTrace();
        } finally {
            try {
                connection.close();
            } catch (SQLException se) {
            }
            try {
                statement.close();
            } catch (SQLException se) {
            }
        }
    }

    private static String createTable(String tableName) {
        StringBuilder sql = new StringBuilder();
        sql.append("CREATE TABLE " + tableName + " (");
        sql.append("id INTEGER not NULL, ");
        sql.append("name VARCHAR(255), ");
        sql.append("url VARCHAR(2048), ");
        sql.append("children VARCHAR(255), ");
        sql.append("PRIMARY KEY ( id ))");
        return sql.toString();
    }

    private static String insertPerson(String tableName, Person person) {
        StringBuilder sql = new StringBuilder();
        sql.append("INSERT INTO genealogicaltree." + tableName);
        sql.append("(id, name, url, nameUrl, children, parents, numberGeneration) \n VALUES (");
        sql.append(person.getId() + ",");
        sql.append("'" + person.getName() + "',");
        sql.append("'" + person.getUrl() + "',");
        sql.append("'" + person.getChildren() + "',");
        sql.append(");");
        return sql.toString();
    }
}

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

private static void saveResultAndQuit(GenealogicalTree tree) throws Exception {
    Timestamp timestamp = new Timestamp(System.currentTimeMillis());
    String tableName = "generate" + timestamp.getTime();
    MySqlHelper.saveTree(tableName, tree.getGenealogicalTree());
}

Разбор первых результатов

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

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

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

Доработаем метод getChildrenUrl() определения страниц детей, чтобы исключить заведомо ошибочные. Чтобы не попадала 1 категория, нужно убрать те ссылки, текстовое содержимое которых начинается на цифру. Чтобы не попадала 2 категория, нужно убрать те ссылки, класс которых равен extiw. Чтобы не попадали 3-4 категории, необходимо исключить ссылки, родительский тег которых равен sup (уточняющие ссылки). Чтобы убрать из списка 5 категорию необходимо исключить ссылки, класс которых равен new (создание страницы).

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

driver.navigate().to("https://ru.wikipedia.org/wiki/Ярослав_Святославич");
children = page.getChildrenUrl();
assertTrue(children.size() == 3);

driver.navigate().to("https://ru.wikipedia.org/wiki/Людовик_VII");
children = page.getChildrenUrl();
assertTrue(children.size() == 5);

driver.navigate().to("https://ru.wikipedia.org/wiki/Галеран_IV_де_Бомон,_граф_де_Мёлан");
children = page.getChildrenUrl();
assertTrue(children.size() == 0);

driver.navigate().to("https://ru.wikipedia.org/wiki/Юрий_Ярославич_(князь_туровский)");
children = page.getChildrenUrl();
assertTrue(children.size() == 5);

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

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

public List<Person> getChildrenUrl() throws MalformedURLException {
    waitLoadPage();
    List<WebElement> childrenLinks = getChildrenLinks();
    List<Person> children = new ArrayList<Person>();
    for (WebElement link : childrenLinks) {
        if (DriverHelper.isSup(link)) {
            continue;
        }
        Person person = new Person(link.getAttribute("href"));
        person.setNameUrl(link.getText());
        if (person.isCorrectNameUrl()) {
            children.add(person);
        }
    }
    return children;
}

private List<WebElement> getChildrenLinks() {
    List<WebElement> childrenLinks = DriverHelper.getElements(driver,
        By.xpath("//table[contains(@class, 'infobox')]//tr[th[.='Дети:']]" +
                "//a[not(@class='new' or @class='extiw')]"));
    return childrenLinks;
}

private void waitLoadPage() {
    this.driver.findElement(By.cssSelector("#firstHeading"));
}

public final class DriverHelper {
    /**
     * Возвращает список элементов без ожидания их появления.<br>
     * По умолчанию установлено неявное ожидание - это значит, что если на
     * странице нет заданных элементов, то пустой результат будет выведен не
     * сразу, а через таймаут, что приведет к потере времени. Чтобы не терять
     * время создан этот метод, где неявное ожидание обнуляется, а после поиска
     * восстанавливается.
     */
    public static List<WebElement> getElements(WebDriver driver, By by) {
        driver.manage().timeouts().implicitlyWait(0, TimeUnit.SECONDS);
        List<WebElement> result = driver.findElements(by);
        driver.manage().timeouts().implicitlyWait(DriverHelper.TIMEOUT, TimeUnit.SECONDS);
        return result;
    }

    public static boolean isSup(WebElement element) {
        String parentTagName = element.findElement(By.xpath(".//..")).getTagName();
        return parentTagName.equals("sup");
    }
}

public class Person {
    private String nameUrl;

    public boolean isCorrectNameUrl() {
        Pattern p = Pattern.compile("^[\\D]+.+");
        Matcher m = p.matcher(nameUrl);
        return m.matches();
    }
}

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

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

Романовы

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

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

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

Эти ошибочные страницы — следствие урлов с якорями, когда у ребенка нет отдельной страницы, а информация о нём хранится либо на странице родителя, как в первом случае, либо на отдельной странице для всех детей — как во втором.

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

public List<Person> getChildrenUrl() {
    waitLoadPage();
    if (DriverHelper.hasAnchor(driver)) {
        return new ArrayList<Person>();
    }
    ...
}

public final class DriverHelper {
    ...
    public static boolean hasAnchor(WebDriver driver) throws MalformedURLException {
        URL url = new URL(driver.getCurrentUrl());
        return url.getRef() != null;
    }
    ...
}

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

@Test
public void testEmptyChildrenInPersonWithAnchor() throws Exception {
    driver.navigate().to("https://ru.wikipedia.org/wiki/Владимир_Александрович");
    PersonPage page = new PersonPage(driver);
    List<String> children = page.getChildrenUrl();
    assertTrue(children.size() == 5);

    driver.navigate().to(
        "https://ru.wikipedia.org/wiki/Владимир_Александрович#.D0.A1.D0.B5.D0.BC.D1.8C.D1.8F");
    children = page.getChildrenUrl();
    assertTrue(children.size() == 0);
}

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

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

Вычисление имени по «якорю»

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

private String getName() throws MalformedURLException {
    waitLoadPage();
    String namePage = driver.findElement(By.cssSelector("#firstHeading")).getText();

    if (!DriverHelper.hasAnchor(driver)) {
        return namePage;
    }

    String anchor = DriverHelper.getAnchor(driver);
    List<WebElement> list = DriverHelper.getElements(driver, By.id(anchor));

    if (list.size() == 0) {
        return namePage;
    }

    String name = list.get(0).getText().trim();
    return name.isEmpty() ? namePage : name;
}

public final class DriverHelper {
    ...
    public static String getAnchor(WebDriver driver) throws MalformedURLException {
        URL url = new URL(driver.getCurrentUrl());
        return url.getRef();
    }
    ...
}

Если текущий 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 поля для номера поколения и списка родителей (чтобы легче было построить возрастающую связь):

private List<Integer> parents = new ArrayList<Integer>();
private int numberGeneration = 0;

public void setParent(int parent) {
    parents.add(parent);
}

public void setNumberGeneration(int numberGeneration) {
    if (this.numberGeneration == 0) {
        this.numberGeneration = numberGeneration;
    }
}

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

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

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

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

public void setChildren(List<Person> children) {
    if (isCurrentPersonDeleted) {
        throw new IllegalArgumentException(
            "Нельзя установить детей удаленной персоне. Текущая персона уже другая");
    }

    Person currentPerson = allPersons.get(indexCurrentUnvisitedPerson);
    int numberGeneration = currentPerson.getNumberGeneration();
    numberGeneration++;
    int idParent = currentPerson.getId();
    for (Person person : children) {
        int index = allPersons.indexOf(person);
        int id;
        if (index >= 0) { // Непервый родитель, номер поколения не трогаем
            allPersons.get(index).setParent(idParent);
            id = allPersons.get(index).getId();
        } else { // Первый родитель
            person.setNumberGeneration(numberGeneration);
            person.setParent(idParent);
            allPersons.add(person);
            id = person.getId();
        }
        currentPerson.setChild(id);
    }
}

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

Итоговые результаты

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

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

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

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

Исходный код проекта