8.5. Основы Kotlin. Графы

Перегрузка операторов

Рассмотрим теперь вот это определение:

private operator fun get(name: String) = vertices[name] ?: throw IllegalArgumentException()

Ключевое слово operator в определении означает, что данная функция переопределяет (перегружает) работу того или иного оператора. Конкретный оператор в Котлине привязывается к названию функции. Функции get соответствует оператор индексации, то есть, имея граф g, мы сможем достать у него вершину по имени с помощью g[name].

В теле функции мы обращаемся к карте vertices, получая из неё Vertex?. Далее вновь используется Элвис-оператор, в правой части которого генерируется исключение, прекращающее работу функции. Это означает, что данная функция, вместо того чтобы вернуть null в случае, когда соответствующего ключа нет в карте, бросает исключение IllegalArgumentException. Зато результат функции становится Vertex (без ?).

Следующий фрагмент использует перегруженный оператор индексации:

fun connect(first: String, second: String) = connect(this[first], this[second])

Данная функция вызывает другую функцию connect — с параметрами типа Vertex вместо String. Для преобразования имени вершины first к самой вершине используется this[first]. this здесь — ключевое слово (этот), обозначающее граф-получатель, то есть тот граф, для которого вызвана функция connect. this[first] вместе использует индексацию на графе.

Поиск на графе

Алгоритмы поиска на графе могут иметь различную цель. Мы рассмотрим их на примере определения расстояния между вершинами. Расстояние между вершинами A и B на графе определяется как минимальное число рёбер, по которым нужно пройти для того, чтобы попасть из A в B. См. пример:

Здесь расстояние между вершинами A и B равно 1, между A и E — 2, между C и F — 3.

Для определения расстояния нужно в том или ином порядке рассмотреть все цепочки рёбер, начинающихся в вершине A, найти те из них, которые заканчиваются в B и определить самую короткую цепочку. Есть два варианта рассмотрения таких цепочек — поиск в глубину и поиск в ширину.

При поиске в глубину мы от каждой вершины переходим к одной из её соседок, формируя всё более и более длинную цепочку. Цепочка прерывается, когда мы попадём в вершину B, или когда мы попадём в одну из уже имеющихся в цепочке вершин, образуя кольцо. После этого мы возвращаемся по цепочке на шаг назад и начинаем пробовать другие цепочки — и так далее.

Поиск в ширину идёт “волнами”. Вначале мы перебираем всех соседок вершины A, запоминая расстояние до каждой из них (1). Затем мы перебираем всех соседок соседок вершины A, имея уже расстояние в 2 ребра. Затем происходит перебор вершин на расстоянии 3 и так далее, пока мы не уткнёмся в вершину B.

Реализация поиска в глубину

DFS = Depth-First Search.

fun dfs(start: String, finish: String): Int = dfs(this[start], this[finish], setOf()) ?: -1

    private fun dfs(start: Vertex, finish: Vertex, visited: Set<Vertex>): Int? =
            if (start == finish) 0
            else {
                val min = start.neighbors
                        .filter { it !in visited }
                        .mapNotNull { dfs(it, finish, visited + start) }
                        .min()
                if (min == null) null else min + 1
            }

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

1. Расстояние от любой вершины до самой себя равно 0.
2. Пусть N(A) — все вершины, соседние с A. Тогда distance(A, B) = min(distance(N, B)) + 1, где минимум выбирается среди всех вершин N, входящих в N(A).

Наивная реализация этих правил могла бы выглядеть вот так:

private fun dfs(start: Vertex, finish: Vertex): Int? =
        if (start == finish) 0
        else {
            val min = start.neighbors.mapNotNull { dfs(it, finish) }.min()
            if (min == null) null else min + 1
        }

Предполагается, что результат этой функции равен null при отсутствии соединения между вершинами (например, если у стартовой вершины нет соседей). Функция высшего порядка mapNotNull при этом вызывает dfs на всех соседях и фильтрует получаемые результаты, удаляя из них все значения, равные null. Вызов mapNotNull в данном случае эквивалентен последовательности вызовов map { dfs(it, finish) }.filterNotNull().

Применение данной функции на практике приведёт к исключению StackOverflowException из-за бесконечной рекурсии, так как имеющаяся схема не препятствует нам бесконечно ходить из стартовой вершины в соседнюю к ней и обратно.

Именно поэтому в функцию было введено множество уже посещённых вершин (третьим параметром, изначально он пуст). Уже посещённые вершины исключаются из множества соседей с помощью filter { it !in visited }, а при рекурсивном вызове функции в это множество добавляется только что посещённая вершина. Это обеспечивает конечность работы функции поиска.

Реализация поиска в ширину

BFS = Breadth-First Search.

fun bfs(start: String, finish: String) = bfs(this[start], this[finish])

private fun bfs(start: Vertex, finish: Vertex): Int {
    val queue = ArrayDeque<Vertex>()
    queue.add(start)
    val visited = mutableMapOf(start to 0)
    while (queue.isNotEmpty()) {
        val next = queue.poll()
        val distance = visited[next]!!
        if (next == finish) return distance
        for (neighbor in next.neighbors) {
            if (neighbor in visited) continue
            visited.put(neighbor, distance + 1)
            queue.add(neighbor)
        }
    }
    return -1
}

В процессе выполнения поиска в ширину мы используем очередь вершин ArrayQueue<Vertex>. Принцип функционирования очереди подобен настоящей очереди в магазине — вызов функции queue.add добавляет вершину-аргумент в конец очереди (увеличивая размер очереди на 1), а вызов функции queue.poll, наоборот, достаёт из головы очереди первую вершину (уменьшая размер на 1). Для пустой очереди результат queue.poll будет равен null. Изначально в очередь записывается только стартовая вершина.

Для хранения найденных расстояний до уже посещённых вершин функция использует ассоциативный массив, ключом в котором является вершина, а значением — расстояние до неё. Изначально нам известно, что расстояние от стартовой вершины до неё же равно 0.

Далее функция последовательно достаёт вершину из очереди и расстояние до неё из массива. В цикле перебираются все вершины, соседние с данной. Происходит проверка, что в вершине мы ещё не были, после чего она записываются в очередь. В качестве расстояния до соседней вершины записывается расстояние до исходной + 1. Эта процедура повторяется до тех пор, пока мы не попадём в искомую вершину finish.

Обратите внимание на оператор val distance = visited[next]!!. Здесь visited[next] обращается по индексу к ассоциативному массиву и имеет результат Int? (Int или null). Мы же хотим получить просто Int. Поскольку в функции постановка вершины в очередь и запись расстояния для неё выполняются всегда друг за другом, мы уверены, что по данному индексу в массиве имеется какое-то значение. Поэтому мы можем применить оператор !!для преобразования типа из Int? в Int. Если всё же окажется, что значения по данному индексу в массиве нет, в этом месте произойдёт исключение KotlinNullPointerException.